Fix for http://bugzilla.opendarwin.org/show_bug.cgi?id=3942 and marquee problems...
[WebKit-https.git] / WebCore / khtml / rendering / render_layer.cpp
1 /*
2  * Copyright (C) 2003 Apple Computer, Inc.
3  *
4  * Portions are Copyright (C) 1998 Netscape Communications Corporation.
5  *
6  * Other contributors:
7  *   Robert O'Callahan <roc+@cs.cmu.edu>
8  *   David Baron <dbaron@fas.harvard.edu>
9  *   Christian Biesinger <cbiesinger@web.de>
10  *   Randall Jesup <rjesup@wgate.com>
11  *   Roland Mainz <roland.mainz@informatik.med.uni-giessen.de>
12  *   Josh Soref <timeless@mac.com>
13  *   Boris Zbarsky <bzbarsky@mit.edu>
14  *
15  * This library is free software; you can redistribute it and/or
16  * modify it under the terms of the GNU Lesser General Public
17  * License as published by the Free Software Foundation; either
18  * version 2.1 of the License, or (at your option) any later version.
19  *
20  * This library is distributed in the hope that it will be useful,
21  * but WITHOUT ANY WARRANTY; without even the implied warranty of
22  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
23  * Lesser General Public License for more details.
24  *
25  * You should have received a copy of the GNU Lesser General Public
26  * License along with this library; if not, write to the Free Software
27  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
28  *
29  * Alternatively, the contents of this file may be used under the terms
30  * of either the Mozilla Public License Version 1.1, found at
31  * http://www.mozilla.org/MPL/ (the "MPL") or the GNU General Public
32  * License Version 2.0, found at http://www.fsf.org/copyleft/gpl.html
33  * (the "GPL"), in which case the provisions of the MPL or the GPL are
34  * applicable instead of those above.  If you wish to allow use of your
35  * version of this file only under the terms of one of those two
36  * licenses (the MPL or the GPL) and not to allow others to use your
37  * version of this file under the LGPL, indicate your decision by
38  * deletingthe provisions above and replace them with the notice and
39  * other provisions required by the MPL or the GPL, as the case may be.
40  * If you do not delete the provisions above, a recipient may use your
41  * version of this file under any of the LGPL, the MPL or the GPL.
42  */
43
44 #include "render_layer.h"
45 #include <kdebug.h>
46 #include <assert.h>
47 #include "khtmlview.h"
48 #include "render_canvas.h"
49 #include "render_arena.h"
50 #include "xml/dom_docimpl.h"
51 #include "xml/dom2_eventsimpl.h"
52 #include "html/html_blockimpl.h"
53
54 #include <qscrollbar.h>
55 #include <qptrvector.h>
56
57 #if APPLE_CHANGES
58 #include "KWQKHTMLPart.h" // For Dashboard.
59 #endif
60
61 // These match the numbers we use over in WebKit (WebFrameView.m).
62 #define LINE_STEP   40
63 #define PAGE_KEEP   40
64
65 using namespace DOM;
66 using namespace khtml;
67
68 #ifdef APPLE_CHANGES
69 QScrollBar* RenderLayer::gScrollBar = 0;
70 #endif
71
72 #ifndef NDEBUG
73 static bool inRenderLayerDetach;
74 #endif
75
76 void* ClipRects::operator new(size_t sz, RenderArena* renderArena) throw()
77 {
78     return renderArena->allocate(sz);
79 }
80
81 void ClipRects::operator delete(void* ptr, size_t sz)
82 {
83     // Stash size where detach can find it.
84     *(size_t *)ptr = sz;
85 }
86
87 void ClipRects::detach(RenderArena* renderArena)
88 {
89     delete this;
90     
91     // Recover the size left there for us by operator delete and free the memory.
92     renderArena->free(*(size_t *)this, this);
93 }
94
95 void
96 RenderScrollMediator::slotValueChanged(int val)
97 {
98     m_layer->updateScrollPositionFromScrollbars();
99 }
100
101 RenderLayer::RenderLayer(RenderObject* object)
102 : m_object( object ),
103 m_parent( 0 ),
104 m_previous( 0 ),
105 m_next( 0 ),
106 m_first( 0 ),
107 m_last( 0 ),
108 m_relX( 0 ),
109 m_relY( 0 ),
110 m_x( 0 ),
111 m_y( 0 ),
112 m_width( 0 ),
113 m_height( 0 ),
114 m_scrollX( 0 ),
115 m_scrollY( 0 ),
116 m_scrollWidth( 0 ),
117 m_scrollHeight( 0 ),
118 m_hBar( 0 ),
119 m_vBar( 0 ),
120 m_scrollMediator( 0 ),
121 m_posZOrderList( 0 ),
122 m_negZOrderList( 0 ),
123 m_clipRects( 0 ) ,
124 m_scrollDimensionsDirty( true ),
125 m_zOrderListsDirty( true ),
126 m_usedTransparency( false ),
127 m_marquee( 0 )
128 {
129 }
130
131 RenderLayer::~RenderLayer()
132 {
133     // Child layers will be deleted by their corresponding render objects, so
134     // our destructor doesn't have to do anything.
135     delete m_hBar;
136     delete m_vBar;
137     delete m_scrollMediator;
138     delete m_posZOrderList;
139     delete m_negZOrderList;
140     delete m_marquee;
141     
142     // Make sure we have no lingering clip rects.
143     assert(!m_clipRects);
144 }
145
146 void RenderLayer::computeRepaintRects()
147 {
148     // FIXME: Child object could override visibility.
149     if (m_object->style()->visibility() == VISIBLE)
150         m_object->getAbsoluteRepaintRectIncludingFloats(m_repaintRect, m_fullRepaintRect);
151     for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
152         child->computeRepaintRects();
153 }
154
155 void RenderLayer::updateLayerPositions(bool doFullRepaint, bool checkForRepaint)
156 {
157     if (doFullRepaint) {
158         m_object->repaint();
159         checkForRepaint = doFullRepaint = false;
160     }
161     
162     updateLayerPosition(); // For relpositioned layers or non-positioned layers,
163                            // we need to keep in sync, since we may have shifted relative
164                            // to our parent layer.
165
166     if (m_hBar || m_vBar) {
167         // Need to position the scrollbars.
168         int x = 0;
169         int y = 0;
170         convertToLayerCoords(root(), x, y);
171         QRect layerBounds = QRect(x,y,width(),height());
172         positionScrollbars(layerBounds);
173     }
174
175     // FIXME: Child object could override visibility.
176     if (checkForRepaint && (m_object->style()->visibility() == VISIBLE))
177         m_object->repaintAfterLayoutIfNeeded(m_repaintRect, m_fullRepaintRect);
178     
179     for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
180         child->updateLayerPositions(doFullRepaint, checkForRepaint);
181         
182     // With all our children positioned, now update our marquee if we need to.
183     if (m_marquee)
184         m_marquee->updateMarqueePosition();
185 }
186
187 void RenderLayer::updateLayerPosition()
188 {
189     // Clear our cached clip rect information.
190     clearClipRect();
191
192     // The canvas is sized to the docWidth/Height over in RenderCanvas::layout, so we
193     // don't need to ever update our layer position here.
194     if (renderer()->isCanvas())
195         return;
196     
197     int x = m_object->xPos();
198     int y = m_object->yPos();
199
200     if (!m_object->isPositioned()) {
201         // We must adjust our position by walking up the render tree looking for the
202         // nearest enclosing object with a layer.
203         RenderObject* curr = m_object->parent();
204         while (curr && !curr->layer()) {
205             x += curr->xPos();
206             y += curr->yPos();
207             curr = curr->parent();
208         }
209     }
210
211     m_relX = m_relY = 0;
212     if (m_object->isRelPositioned()) {
213         static_cast<RenderBox*>(m_object)->relativePositionOffset(m_relX, m_relY);
214         x += m_relX; y += m_relY;
215     }
216     
217     // Subtract our parent's scroll offset.
218     if (m_object->isPositioned() && enclosingPositionedAncestor()) {
219         RenderLayer* positionedParent = enclosingPositionedAncestor();
220
221         // For positioned layers, we subtract out the enclosing positioned layer's scroll offset.
222         positionedParent->subtractScrollOffset(x, y);
223         
224         if (m_object->isPositioned() && positionedParent->renderer()->isRelPositioned() &&
225             positionedParent->renderer()->isInlineFlow()) {
226             // When we have an enclosing relpositioned inline, we need to add in the offset of the first line
227             // box from the rest of the content, but only in the cases where we know we're positioned
228             // relative to the inline itself.
229             RenderFlow* flow = static_cast<RenderFlow*>(positionedParent->renderer());
230             int sx = 0, sy = 0;
231             if (flow->firstLineBox()) {
232                 sx = flow->firstLineBox()->xPos();
233                 sy = flow->firstLineBox()->yPos();
234             }
235             else {
236                 sx = flow->staticX();
237                 sy = flow->staticY();
238             }
239             bool isInlineType = m_object->style()->isOriginalDisplayInlineType();
240             
241             if (!m_object->hasStaticX())
242                 x += sx;
243             
244             // This is not terribly intuitive, but we have to match other browsers.  Despite being a block display type inside
245             // an inline, we still keep our x locked to the left of the relative positioned inline.  Arguably the correct
246             // behavior would be to go flush left to the block that contains the inline, but that isn't what other browsers
247             // do.
248             if (m_object->hasStaticX() && !isInlineType)
249                 // Avoid adding in the left border/padding of the containing block twice.  Subtract it out.
250                 x += sx - (m_object->containingBlock()->borderLeft() + m_object->containingBlock()->paddingLeft());
251             
252             if (!m_object->hasStaticY())
253                 y += sy;
254         }
255     }
256     else if (parent())
257         parent()->subtractScrollOffset(x, y);
258     
259     setPos(x,y);
260
261     setWidth(m_object->width());
262     setHeight(m_object->height());
263
264     if (!m_object->hasOverflowClip()) {
265         if (m_object->overflowWidth() > m_object->width())
266             setWidth(m_object->overflowWidth());
267         if (m_object->overflowHeight() > m_object->height())
268             setHeight(m_object->overflowHeight());
269     }    
270 }
271
272 RenderLayer *RenderLayer::stackingContext() const
273 {
274     RenderLayer* curr = parent();
275     for ( ; curr && !curr->m_object->isCanvas() && !curr->m_object->isRoot() &&
276           curr->m_object->style()->hasAutoZIndex();
277           curr = curr->parent());
278     return curr;
279 }
280
281 RenderLayer*
282 RenderLayer::enclosingPositionedAncestor() const
283 {
284     RenderLayer* curr = parent();
285     for ( ; curr && !curr->m_object->isCanvas() && !curr->m_object->isRoot() &&
286          !curr->m_object->isPositioned() && !curr->m_object->isRelPositioned();
287          curr = curr->parent());
288          
289     return curr;
290 }
291
292 #if APPLE_CHANGES
293 bool
294 RenderLayer::isTransparent()
295 {
296     return m_object->style()->opacity() < 1.0f;
297 }
298
299 RenderLayer*
300 RenderLayer::transparentAncestor()
301 {
302     RenderLayer* curr = parent();
303     for ( ; curr && curr->m_object->style()->opacity() == 1.0f; curr = curr->parent());
304     return curr;
305 }
306
307 void RenderLayer::beginTransparencyLayers(QPainter* p)
308 {
309     if (isTransparent() && m_usedTransparency)
310         return;
311     
312     RenderLayer* ancestor = transparentAncestor();
313     if (ancestor)
314         ancestor->beginTransparencyLayers(p);
315     
316     if (isTransparent()) {
317         m_usedTransparency = true;
318         p->beginTransparencyLayer(renderer()->style()->opacity());
319     }
320 }
321
322 #endif
323
324 void* RenderLayer::operator new(size_t sz, RenderArena* renderArena) throw()
325 {
326     return renderArena->allocate(sz);
327 }
328
329 void RenderLayer::operator delete(void* ptr, size_t sz)
330 {
331     assert(inRenderLayerDetach);
332     
333     // Stash size where detach can find it.
334     *(size_t *)ptr = sz;
335 }
336
337 void RenderLayer::detach(RenderArena* renderArena)
338 {
339 #ifndef NDEBUG
340     inRenderLayerDetach = true;
341 #endif
342     delete this;
343 #ifndef NDEBUG
344     inRenderLayerDetach = false;
345 #endif
346     
347     // Recover the size left there for us by operator delete and free the memory.
348     renderArena->free(*(size_t *)this, this);
349 }
350
351 void RenderLayer::addChild(RenderLayer *child, RenderLayer* beforeChild)
352 {
353     RenderLayer* prevSibling = beforeChild ? beforeChild->previousSibling() : lastChild();
354     if (prevSibling) {
355         child->setPreviousSibling(prevSibling);
356         prevSibling->setNextSibling(child);
357     }
358     else
359         setFirstChild(child);
360
361     if (beforeChild) {
362         beforeChild->setPreviousSibling(child);
363         child->setNextSibling(beforeChild);
364     }
365     else
366         setLastChild(child);
367    
368     child->setParent(this);
369
370     // Dirty the z-order list in which we are contained.  The stackingContext() can be null in the
371     // case where we're building up generated content layers.  This is ok, since the lists will start
372     // off dirty in that case anyway.
373     RenderLayer* stackingContext = child->stackingContext();
374     if (stackingContext)
375         stackingContext->dirtyZOrderLists();
376 }
377
378 RenderLayer* RenderLayer::removeChild(RenderLayer* oldChild)
379 {
380     // remove the child
381     if (oldChild->previousSibling())
382         oldChild->previousSibling()->setNextSibling(oldChild->nextSibling());
383     if (oldChild->nextSibling())
384         oldChild->nextSibling()->setPreviousSibling(oldChild->previousSibling());
385
386     if (m_first == oldChild)
387         m_first = oldChild->nextSibling();
388     if (m_last == oldChild)
389         m_last = oldChild->previousSibling();
390
391     // Dirty the z-order list in which we are contained.  When called via the
392     // reattachment process in removeOnlyThisLayer, the layer may already be disconnected
393     // from the main layer tree, so we need to null-check the |stackingContext| value.
394     RenderLayer* stackingContext = oldChild->stackingContext();
395     if (stackingContext)
396         oldChild->stackingContext()->dirtyZOrderLists();
397     
398     oldChild->setPreviousSibling(0);
399     oldChild->setNextSibling(0);
400     oldChild->setParent(0);
401     
402     return oldChild;
403 }
404
405 void RenderLayer::removeOnlyThisLayer()
406 {
407     if (!m_parent)
408         return;
409     
410     // Dirty the clip rects.
411     clearClipRects();
412
413     // Remove us from the parent.
414     RenderLayer* parent = m_parent;
415     RenderLayer* nextSib = nextSibling();
416     parent->removeChild(this);
417     
418     // Now walk our kids and reattach them to our parent.
419     RenderLayer* current = m_first;
420     while (current) {
421         RenderLayer* next = current->nextSibling();
422         removeChild(current);
423         parent->addChild(current, nextSib);
424         current = next;
425     }
426     
427     detach(renderer()->renderArena());
428 }
429
430 void RenderLayer::insertOnlyThisLayer()
431 {
432     if (!m_parent && renderer()->parent()) {
433         // We need to connect ourselves when our renderer() has a parent.
434         // Find our enclosingLayer and add ourselves.
435         RenderLayer* parentLayer = renderer()->parent()->enclosingLayer();
436         if (parentLayer)
437             parentLayer->addChild(this, 
438                                   renderer()->parent()->findNextLayer(parentLayer, renderer()));
439     }
440     
441     // Remove all descendant layers from the hierarchy and add them to the new position.
442     for (RenderObject* curr = renderer()->firstChild(); curr; curr = curr->nextSibling())
443         curr->moveLayers(m_parent, this);
444         
445     // Clear out all the clip rects.
446     clearClipRects();
447 }
448
449 void 
450 RenderLayer::convertToLayerCoords(const RenderLayer* ancestorLayer, int& x, int& y) const
451 {
452     if (ancestorLayer == this)
453         return;
454         
455     if (m_object->style()->position() == FIXED) {
456         // Add in the offset of the view.  We can obtain this by calling
457         // absolutePosition() on the RenderCanvas.
458         int xOff, yOff;
459         m_object->absolutePosition(xOff, yOff, true);
460         x += xOff;
461         y += yOff;
462         return;
463     }
464  
465     RenderLayer* parentLayer;
466     if (m_object->style()->position() == ABSOLUTE)
467         parentLayer = enclosingPositionedAncestor();
468     else
469         parentLayer = parent();
470     
471     if (!parentLayer) return;
472     
473     parentLayer->convertToLayerCoords(ancestorLayer, x, y);
474
475     x += xPos();
476     y += yPos();
477 }
478
479 void
480 RenderLayer::scrollOffset(int& x, int& y)
481 {
482     x += scrollXOffset();
483     y += scrollYOffset();
484 }
485
486 void
487 RenderLayer::subtractScrollOffset(int& x, int& y)
488 {
489     x -= scrollXOffset();
490     y -= scrollYOffset();
491 }
492
493 void
494 RenderLayer::scrollToOffset(int x, int y, bool updateScrollbars, bool repaint)
495 {
496     if (renderer()->style()->overflow() != OMARQUEE) {
497         if (x < 0) x = 0;
498         if (y < 0) y = 0;
499     
500         // Call the scrollWidth/Height functions so that the dimensions will be computed if they need
501         // to be (for overflow:hidden blocks).
502         int maxX = scrollWidth() - m_object->clientWidth();
503         int maxY = scrollHeight() - m_object->clientHeight();
504         
505         if (x > maxX) x = maxX;
506         if (y > maxY) y = maxY;
507     }
508     
509     // FIXME: Eventually, we will want to perform a blit.  For now never
510     // blit, since the check for blitting is going to be very
511     // complicated (since it will involve testing whether our layer
512     // is either occluded by another layer or clipped by an enclosing
513     // layer or contains fixed backgrounds, etc.).
514     m_scrollX = x;
515     m_scrollY = y;
516
517     // Update the positions of our child layers.
518     for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
519         child->updateLayerPositions(false, false);
520     
521 #if APPLE_CHANGES
522     // Move our widgets.
523     m_object->updateWidgetPositions();
524     
525     // Update dashboard regions, scrolling may change the clip of a
526     // particular region.
527     RenderCanvas *canvas = renderer()->canvas();
528     if (canvas)
529         canvas->view()->updateDashboardRegions();
530 #endif
531
532     // Fire the scroll DOM event.
533     m_object->element()->dispatchHTMLEvent(EventImpl::SCROLL_EVENT, true, false);
534
535     // Just schedule a full repaint of our object.
536     if (repaint)
537         m_object->repaint();
538     
539     if (updateScrollbars) {
540         if (m_hBar)
541             m_hBar->setValue(m_scrollX);
542         if (m_vBar)
543             m_vBar->setValue(m_scrollY);
544     }
545 }
546
547 void
548 RenderLayer::updateScrollPositionFromScrollbars()
549 {
550     bool needUpdate = false;
551     int newX = m_scrollX;
552     int newY = m_scrollY;
553     
554     if (m_hBar) {
555         newX = m_hBar->value();
556         if (newX != m_scrollX)
557            needUpdate = true;
558     }
559
560     if (m_vBar) {
561         newY = m_vBar->value();
562         if (newY != m_scrollY)
563            needUpdate = true;
564     }
565
566     if (needUpdate)
567         scrollToOffset(newX, newY, false);
568 }
569
570 void
571 RenderLayer::setHasHorizontalScrollbar(bool hasScrollbar)
572 {
573     if (hasScrollbar && !m_hBar) {
574         QScrollView* scrollView = m_object->element()->getDocument()->view();
575         m_hBar = new QScrollBar(Qt::Horizontal, 0);
576         scrollView->addChild(m_hBar, 0, -50000);
577         if (!m_scrollMediator)
578             m_scrollMediator = new RenderScrollMediator(this);
579         m_scrollMediator->connect(m_hBar, SIGNAL(valueChanged(int)), SLOT(slotValueChanged(int)));
580     }
581     else if (!hasScrollbar && m_hBar) {
582         QScrollView* scrollView = m_object->element()->getDocument()->view();
583         scrollView->removeChild (m_hBar);
584
585         m_scrollMediator->disconnect(m_hBar, SIGNAL(valueChanged(int)),
586                                      m_scrollMediator, SLOT(slotValueChanged(int)));
587         delete m_hBar;
588         m_hBar = 0;
589     }
590 }
591
592 void
593 RenderLayer::setHasVerticalScrollbar(bool hasScrollbar)
594 {
595     if (hasScrollbar && !m_vBar) {
596         QScrollView* scrollView = m_object->element()->getDocument()->view();
597         m_vBar = new QScrollBar(Qt::Vertical, 0);
598         scrollView->addChild(m_vBar, 0, -50000);
599         if (!m_scrollMediator)
600             m_scrollMediator = new RenderScrollMediator(this);
601         m_scrollMediator->connect(m_vBar, SIGNAL(valueChanged(int)), SLOT(slotValueChanged(int)));
602     }
603     else if (!hasScrollbar && m_vBar) {
604         QScrollView* scrollView = m_object->element()->getDocument()->view();
605         scrollView->removeChild (m_vBar);
606         
607         m_scrollMediator->disconnect(m_vBar, SIGNAL(valueChanged(int)),
608                                      m_scrollMediator, SLOT(slotValueChanged(int)));
609         delete m_vBar;
610         m_vBar = 0;
611     }
612 }
613
614 int
615 RenderLayer::verticalScrollbarWidth()
616 {
617     if (!m_vBar)
618         return 0;
619
620     return m_vBar->width();
621 }
622
623 int
624 RenderLayer::horizontalScrollbarHeight()
625 {
626     if (!m_hBar)
627         return 0;
628
629     return m_hBar->height();
630 }
631
632 void
633 RenderLayer::moveScrollbarsAside()
634 {
635     if (m_hBar)
636         m_hBar->move(0, -50000);
637     if (m_vBar)
638         m_vBar->move(0, -50000);
639 }
640
641 void
642 RenderLayer::positionScrollbars(const QRect& absBounds)
643 {
644     if (m_vBar) {
645         m_vBar->move(absBounds.x()+absBounds.width()-m_object->borderRight()-m_vBar->width(),
646                      absBounds.y()+m_object->borderTop());
647         m_vBar->resize(m_vBar->width(), absBounds.height() -
648                        (m_object->borderTop()+m_object->borderBottom()) -
649                        (m_hBar ? m_hBar->height()-1 : 0));
650     }
651
652     if (m_hBar) {
653         m_hBar->move(absBounds.x()+m_object->borderLeft(),
654                      absBounds.y()+absBounds.height()-m_object->borderBottom()-m_hBar->height());
655         m_hBar->resize(absBounds.width() - (m_object->borderLeft()+m_object->borderRight()) -
656                        (m_vBar ? m_vBar->width()-1 : 0),
657                        m_hBar->height());
658     }
659 }
660
661 int RenderLayer::scrollWidth()
662 {
663     if (m_scrollDimensionsDirty)
664         computeScrollDimensions();
665     return m_scrollWidth;
666 }
667
668 int RenderLayer::scrollHeight()
669 {
670     if (m_scrollDimensionsDirty)
671         computeScrollDimensions();
672     return m_scrollHeight;
673 }
674
675 void RenderLayer::computeScrollDimensions(bool* needHBar, bool* needVBar)
676 {
677     m_scrollDimensionsDirty = false;
678
679     int rightPos = m_object->rightmostPosition(true, false) - m_object->borderLeft();
680     int bottomPos = m_object->lowestPosition(true, false) - m_object->borderTop();
681
682     int clientWidth = m_object->clientWidth();
683     int clientHeight = m_object->clientHeight();
684
685     m_scrollWidth = kMax(rightPos, clientWidth);
686     m_scrollHeight = kMax(bottomPos, clientHeight);
687
688     if (needHBar)
689         *needHBar = rightPos > clientWidth;
690     if (needVBar)
691         *needVBar = bottomPos > clientHeight;
692 }
693
694 void
695 RenderLayer::updateScrollInfoAfterLayout()
696 {
697     m_scrollDimensionsDirty = true;
698     if (m_object->style()->overflow() == OHIDDEN)
699         return; // All we had to do was dirty.
700
701     bool needHorizontalBar, needVerticalBar;
702     computeScrollDimensions(&needHorizontalBar, &needVerticalBar);
703
704     if (m_object->style()->overflow() != OMARQUEE) {
705         // Layout may cause us to be in an invalid scroll position.  In this case we need
706         // to pull our scroll offsets back to the max (or push them up to the min).
707         int newX = kMax(0, kMin(m_scrollX, scrollWidth() - m_object->clientWidth()));
708         int newY = kMax(0, kMin(m_scrollY, scrollHeight() - m_object->clientHeight()));
709         if (newX != m_scrollX || newY != m_scrollY)
710             scrollToOffset(newX, newY);
711     }
712
713     bool haveHorizontalBar = m_hBar;
714     bool haveVerticalBar = m_vBar;
715
716     // overflow:scroll should just enable/disable.
717     if (m_object->style()->overflow() == OSCROLL) {
718         m_hBar->setEnabled(needHorizontalBar);
719         m_vBar->setEnabled(needVerticalBar);
720     }
721
722     // overflow:auto may need to lay out again if scrollbars got added/removed.
723     bool scrollbarsChanged = (m_object->hasAutoScrollbars()) &&
724         (haveHorizontalBar != needHorizontalBar || haveVerticalBar != needVerticalBar);    
725     if (scrollbarsChanged) {
726         setHasHorizontalScrollbar(needHorizontalBar);
727         setHasVerticalScrollbar(needVerticalBar);
728        
729 #if APPLE_CHANGES
730         // Force an update since we know the scrollbars have changed things.
731         if (m_object->document()->hasDashboardRegions())
732             m_object->document()->setDashboardRegionsDirty(true);
733 #endif
734
735         m_object->repaint();
736
737         if (m_object->style()->overflow() == OAUTO) {
738             // Our proprietary overflow: overlay value doesn't trigger a layout.
739             m_object->setNeedsLayout(true);
740             if (m_object->isRenderBlock())
741                 static_cast<RenderBlock*>(m_object)->layoutBlock(true);
742             else
743                 m_object->layout();
744         }
745     }
746
747     // Set up the range (and page step/line step).
748     if (m_hBar) {
749         int clientWidth = m_object->clientWidth();
750         int pageStep = (clientWidth-PAGE_KEEP);
751         if (pageStep < 0) pageStep = clientWidth;
752         m_hBar->setSteps(LINE_STEP, pageStep);
753 #ifdef APPLE_CHANGES
754         m_hBar->setKnobProportion(clientWidth, m_scrollWidth);
755 #else
756         m_hBar->setRange(0, m_scrollWidth-clientWidth);
757         m_object->repaintRectangle(QRect(m_object->borderLeft(), m_object->borderTop() + clientHeight(),
758                                    horizontalScrollbarHeight(),
759                                    m_object->width() - m_object->borderLeft() - m_object->borderRight()));
760 #endif
761     }
762     if (m_vBar) {
763         int clientHeight = m_object->clientHeight();
764         int pageStep = (clientHeight-PAGE_KEEP);
765         if (pageStep < 0) pageStep = clientHeight;
766         m_vBar->setSteps(LINE_STEP, pageStep);
767 #ifdef APPLE_CHANGES
768         m_vBar->setKnobProportion(clientHeight, m_scrollHeight);
769 #else
770         m_vBar->setRange(0, m_scrollHeight-clientHeight);
771 #endif
772         m_object->repaintRectangle(QRect(m_object->borderLeft() + m_object->clientWidth(),
773                                    m_object->borderTop(), verticalScrollbarWidth(), 
774                                    m_object->height() - m_object->borderTop() - m_object->borderBottom()));
775     }
776     
777 #if APPLE_CHANGES
778     // Force an update since we know the scrollbars have changed things.
779     if (m_object->document()->hasDashboardRegions())
780         m_object->document()->setDashboardRegionsDirty(true);
781 #endif
782
783     m_object->repaint();
784 }
785
786 #if APPLE_CHANGES
787 void
788 RenderLayer::paintScrollbars(QPainter* p, const QRect& damageRect)
789 {
790     // Move the widgets if necessary.  We normally move and resize widgets during layout, but sometimes
791     // widgets can move without layout occurring (most notably when you scroll a document that
792     // contains fixed positioned elements).
793     if (m_hBar || m_vBar) {
794         int x = 0;
795         int y = 0;
796         convertToLayerCoords(root(), x, y);
797         QRect layerBounds = QRect(x, y, width(), height());
798         positionScrollbars(layerBounds);
799     }
800
801     // Now that we're sure the scrollbars are in the right place, paint them.
802     if (m_hBar)
803         m_hBar->paint(p, damageRect);
804     if (m_vBar)
805         m_vBar->paint(p, damageRect);
806 }
807 #endif
808
809 bool RenderLayer::scroll(KWQScrollDirection direction, KWQScrollGranularity granularity, float multiplier)
810 {
811     bool didHorizontalScroll = false;
812     bool didVerticalScroll = false;
813     
814     if (m_hBar != 0) {
815         if (granularity == KWQScrollDocument) {
816             // Special-case for the KWQScrollDocument granularity. A document scroll can only be up 
817             // or down and in both cases the horizontal bar goes all the way to the left.
818             didHorizontalScroll = m_hBar->scroll(KWQScrollLeft, KWQScrollDocument, multiplier);
819         } else {
820             didHorizontalScroll = m_hBar->scroll(direction, granularity, multiplier);
821         }
822     }
823     if (m_vBar != 0) {
824         didVerticalScroll = m_vBar->scroll(direction, granularity, multiplier);
825     }
826
827     return (didHorizontalScroll || didVerticalScroll);
828 }
829
830 void
831 RenderLayer::paint(QPainter *p, const QRect& damageRect, bool selectionOnly, RenderObject *paintingRoot)
832 {
833     paintLayer(this, p, damageRect, false, selectionOnly, paintingRoot);
834 }
835
836 static void setClip(QPainter* p, const QRect& paintDirtyRect, const QRect& clipRect)
837 {
838     if (paintDirtyRect == clipRect)
839         return;
840
841     p->save();
842     
843 #if APPLE_CHANGES
844     p->addClip(clipRect);
845 #else
846     QRect clippedRect = p->xForm(clipRect);
847     QRegion creg(clippedRect);
848     QRegion old = p->clipRegion();
849     if (!old.isNull())
850         creg = old.intersect(creg);
851     p->setClipRegion(creg);
852 #endif
853     
854 }
855
856 static void restoreClip(QPainter* p, const QRect& paintDirtyRect, const QRect& clipRect)
857 {
858     if (paintDirtyRect == clipRect)
859         return;
860     p->restore();
861 }
862
863 void
864 RenderLayer::paintLayer(RenderLayer* rootLayer, QPainter *p,
865                         const QRect& paintDirtyRect, bool haveTransparency, bool selectionOnly,
866                         RenderObject *paintingRoot)
867 {
868     // Calculate the clip rects we should use.
869     QRect layerBounds, damageRect, clipRectToApply;
870     calculateRects(rootLayer, paintDirtyRect, layerBounds, damageRect, clipRectToApply);
871     int x = layerBounds.x();
872     int y = layerBounds.y();
873                              
874     // Ensure our z-order lists are up-to-date.
875     updateZOrderLists();
876
877 #if APPLE_CHANGES
878     if (isTransparent())
879         haveTransparency = true;
880 #endif
881
882     // If this layer's renderer is a child of the paintingRoot, we render unconditionally, which
883     // is done by passing a nil paintingRoot down to our renderer (as if no paintingRoot was ever set).
884     // Else, our renderer tree may or may not contain the painting root, so we pass that root along
885     // so it will be tested against as we decend through the renderers.
886     RenderObject *paintingRootForRenderer = 0;
887     if (paintingRoot && !m_object->hasAncestor(paintingRoot)) {
888         paintingRootForRenderer = paintingRoot;
889     }
890     
891     // We want to paint our layer, but only if we intersect the damage rect.
892     bool shouldPaint = intersectsDamageRect(layerBounds, damageRect);
893     if (shouldPaint && !selectionOnly && !damageRect.isEmpty()) {
894 #if APPLE_CHANGES
895         // Begin transparency layers lazily now that we know we have to paint something.
896         if (haveTransparency)
897             beginTransparencyLayers(p);
898 #endif
899         
900         // Paint our background first, before painting any child layers.
901         // Establish the clip used to paint our background.
902         setClip(p, paintDirtyRect, damageRect);
903
904         // Paint the background.
905         RenderObject::PaintInfo info(p, damageRect, PaintActionBlockBackground, paintingRootForRenderer);
906         renderer()->paint(info, x - renderer()->xPos(), y - renderer()->yPos());        
907 #if APPLE_CHANGES
908         // Our scrollbar widgets paint exactly when we tell them to, so that they work properly with
909         // z-index.  We paint after we painted the background/border, so that the scrollbars will
910         // sit above the background/border.
911         paintScrollbars(p, damageRect);
912 #endif
913         // Restore the clip.
914         restoreClip(p, paintDirtyRect, damageRect);
915     }
916
917     // Now walk the sorted list of children with negative z-indices.
918     if (m_negZOrderList) {
919         uint count = m_negZOrderList->count();
920         for (uint i = 0; i < count; i++) {
921             RenderLayer* child = m_negZOrderList->at(i);
922             child->paintLayer(rootLayer, p, paintDirtyRect, haveTransparency, selectionOnly, paintingRoot);
923         }
924     }
925     
926     // Now establish the appropriate clip and paint our child RenderObjects.
927     if (shouldPaint && !clipRectToApply.isEmpty()) {
928 #if APPLE_CHANGES
929         // Begin transparency layers lazily now that we know we have to paint something.
930         if (haveTransparency)
931             beginTransparencyLayers(p);
932 #endif
933
934         // Set up the clip used when painting our children.
935         setClip(p, paintDirtyRect, clipRectToApply);
936
937         int tx = x - renderer()->xPos();
938         int ty = y - renderer()->yPos();
939         RenderObject::PaintInfo info(p, clipRectToApply, 
940                                      selectionOnly ? PaintActionSelection : PaintActionChildBlockBackgrounds,
941                                      paintingRootForRenderer);
942         renderer()->paint(info, tx, ty);
943         if (!selectionOnly) {
944             info.phase = PaintActionFloat;
945             renderer()->paint(info, tx, ty);
946             info.phase = PaintActionForeground;
947             renderer()->paint(info, tx, ty);
948             info.phase = PaintActionOutline;
949             renderer()->paint(info, tx, ty);
950         }
951
952         // Now restore our clip.
953         restoreClip(p, paintDirtyRect, clipRectToApply);
954     }
955     
956     // Now walk the sorted list of children with positive z-indices.
957     if (m_posZOrderList) {
958         uint count = m_posZOrderList->count();
959         for (uint i = 0; i < count; i++) {
960             RenderLayer* child = m_posZOrderList->at(i);
961             child->paintLayer(rootLayer, p, paintDirtyRect, haveTransparency, selectionOnly, paintingRoot);
962         }
963     }
964     
965 #if APPLE_CHANGES
966     // End our transparency layer
967     if (isTransparent() && m_usedTransparency) {
968         p->endTransparencyLayer();
969         m_usedTransparency = false;
970     }
971 #endif
972 }
973
974 bool
975 RenderLayer::hitTest(RenderObject::NodeInfo& info, int x, int y)
976 {
977 #if APPLE_CHANGES
978     // Clear our our scrollbar variable
979     RenderLayer::gScrollBar = 0;
980 #endif
981     
982     QRect damageRect(m_x, m_y, width(), height());
983     RenderLayer* insideLayer = hitTestLayer(this, info, x, y, damageRect);
984
985     // Now determine if the result is inside an anchor; make sure an image map wins if
986     // it already set URLElement and only use the innermost.
987     DOM::NodeImpl* node = info.innerNode();
988     while (node) {
989         if (node->isLink() && !info.URLElement())
990             info.setURLElement(node);
991         node = node->parentNode();
992     }
993
994     // Next set up the correct :hover/:active state along the new chain.
995     updateHoverActiveState(info);
996     
997     // Now return whether we were inside this layer (this will always be true for the root
998     // layer).
999     return insideLayer;
1000 }
1001
1002 RenderLayer*
1003 RenderLayer::hitTestLayer(RenderLayer* rootLayer, RenderObject::NodeInfo& info,
1004                           int xMousePos, int yMousePos, const QRect& hitTestRect)
1005 {
1006     // Calculate the clip rects we should use.
1007     QRect layerBounds, bgRect, fgRect;
1008     calculateRects(rootLayer, hitTestRect, layerBounds, bgRect, fgRect);
1009     
1010     // Ensure our z-order lists are up-to-date.
1011     updateZOrderLists();
1012
1013     // This variable tracks which layer the mouse ends up being inside.  The minute we find an insideLayer,
1014     // we are done and can return it.
1015     RenderLayer* insideLayer = 0;
1016     
1017     // Begin by walking our list of positive layers from highest z-index down to the lowest
1018     // z-index.
1019     if (m_posZOrderList) {
1020         uint count = m_posZOrderList->count();
1021         for (int i = count-1; i >= 0; i--) {
1022             RenderLayer* child = m_posZOrderList->at(i);
1023             insideLayer = child->hitTestLayer(rootLayer, info, xMousePos, yMousePos, hitTestRect);
1024             if (insideLayer)
1025                 return insideLayer;
1026         }
1027     }
1028
1029     // Next we want to see if the mouse pos is inside the child RenderObjects of the layer.
1030     if (containsPoint(xMousePos, yMousePos, fgRect) && 
1031         renderer()->hitTest(info, xMousePos, yMousePos,
1032                             layerBounds.x() - renderer()->xPos(),
1033                             layerBounds.y() - renderer()->yPos(), HitTestDescendants)) {
1034         // for positioned generated content, we might still not have a
1035         // node by the time we get to the layer level, since none of
1036         // the content in the layer has an element. So just walk up
1037         // the tree.
1038         if (!info.innerNode()) {
1039             for (RenderObject *r = renderer(); r != NULL; r = r->parent()) { 
1040                 if (r->element()) {
1041                     info.setInnerNode(r->element());
1042                     break;
1043                 }
1044             }
1045         }
1046
1047         if (!info.innerNonSharedNode()) {
1048              for (RenderObject *r = renderer(); r != NULL; r = r->parent()) { 
1049                  if (r->element()) {
1050                      info.setInnerNonSharedNode(r->element());
1051                      break;
1052                  }
1053              }
1054         }
1055         return this;
1056     }
1057         
1058     // Now check our negative z-index children.
1059     if (m_negZOrderList) {
1060         uint count = m_negZOrderList->count();
1061         for (int i = count-1; i >= 0; i--) {
1062             RenderLayer* child = m_negZOrderList->at(i);
1063             insideLayer = child->hitTestLayer(rootLayer, info, xMousePos, yMousePos, hitTestRect);
1064             if (insideLayer)
1065                 return insideLayer;
1066         }
1067     }
1068
1069     // Next we want to see if the mouse pos is inside this layer but not any of its children.
1070     if (containsPoint(xMousePos, yMousePos, bgRect) &&
1071         renderer()->hitTest(info, xMousePos, yMousePos,
1072                             layerBounds.x() - renderer()->xPos(),
1073                             layerBounds.y() - renderer()->yPos(),
1074                             HitTestSelf))
1075         return this;
1076
1077     // No luck.
1078     return 0;
1079 }
1080
1081 void RenderLayer::calculateClipRects(const RenderLayer* rootLayer)
1082 {
1083     if (m_clipRects)
1084         return; // We have the correct cached value.
1085
1086     if (!parent()) {
1087         // The root layer's clip rect is always just its dimensions.
1088         m_clipRects = new (m_object->renderArena()) ClipRects(QRect(0,0,width(),height()));
1089         m_clipRects->ref();
1090         return;
1091     }
1092
1093     // Ensure that our parent's clip has been calculated so that we can examine the values.
1094     parent()->calculateClipRects(rootLayer);
1095
1096     // Set up our three rects to initially match the parent rects.
1097     QRect posClipRect(parent()->clipRects()->posClipRect());
1098     QRect overflowClipRect(parent()->clipRects()->overflowClipRect());
1099     QRect fixedClipRect(parent()->clipRects()->fixedClipRect());
1100
1101     // A fixed object is essentially the root of its containing block hierarchy, so when
1102     // we encounter such an object, we reset our clip rects to the fixedClipRect.
1103     if (m_object->style()->position() == FIXED) {
1104         posClipRect = fixedClipRect;
1105         overflowClipRect = fixedClipRect;
1106     }
1107     else if (m_object->style()->position() == RELATIVE)
1108         posClipRect = overflowClipRect;
1109     
1110     // Update the clip rects that will be passed to child layers.
1111     if (m_object->hasOverflowClip() || m_object->hasClip()) {
1112         // This layer establishes a clip of some kind.
1113         int x = 0;
1114         int y = 0;
1115         convertToLayerCoords(rootLayer, x, y);
1116         
1117         if (m_object->hasOverflowClip()) {
1118             QRect newOverflowClip = m_object->getOverflowClipRect(x,y);
1119             overflowClipRect  = newOverflowClip.intersect(overflowClipRect);
1120             if (m_object->isPositioned() || m_object->isRelPositioned())
1121                 posClipRect = newOverflowClip.intersect(posClipRect);
1122         }
1123         if (m_object->hasClip()) {
1124             QRect newPosClip = m_object->getClipRect(x,y);
1125             posClipRect = posClipRect.intersect(newPosClip);
1126             overflowClipRect = overflowClipRect.intersect(newPosClip);
1127             fixedClipRect = fixedClipRect.intersect(newPosClip);
1128         }
1129     }
1130     
1131     // If our clip rects match our parent's clip, then we can just share its data structure and
1132     // ref count.
1133     if (posClipRect == parent()->clipRects()->posClipRect() &&
1134         overflowClipRect == parent()->clipRects()->overflowClipRect() &&
1135         fixedClipRect == parent()->clipRects()->fixedClipRect())
1136         m_clipRects = parent()->clipRects();
1137     else
1138         m_clipRects = new (m_object->renderArena()) ClipRects(overflowClipRect, fixedClipRect, posClipRect);
1139     m_clipRects->ref();
1140 }
1141
1142 void RenderLayer::calculateRects(const RenderLayer* rootLayer, const QRect& paintDirtyRect, QRect& layerBounds,
1143                                  QRect& backgroundRect, QRect& foregroundRect)
1144 {
1145     if (parent()) {
1146         parent()->calculateClipRects(rootLayer);
1147         backgroundRect = m_object->style()->position() == FIXED ? parent()->clipRects()->fixedClipRect() :
1148                          (m_object->isPositioned() ? parent()->clipRects()->posClipRect() : 
1149                                                      parent()->clipRects()->overflowClipRect());
1150         backgroundRect = backgroundRect.intersect(paintDirtyRect);
1151     } else
1152         backgroundRect = paintDirtyRect;
1153     foregroundRect = backgroundRect;
1154     
1155     int x = 0;
1156     int y = 0;
1157     convertToLayerCoords(rootLayer, x, y);
1158     layerBounds = QRect(x,y,width(),height());
1159     
1160     // Update the clip rects that will be passed to child layers.
1161     if (m_object->hasOverflowClip() || m_object->hasClip()) {
1162         // This layer establishes a clip of some kind.
1163         if (m_object->hasOverflowClip())
1164             foregroundRect = foregroundRect.intersect(m_object->getOverflowClipRect(x,y));
1165         if (m_object->hasClip()) {
1166             // Clip applies to *us* as well, so go ahead and update the damageRect.
1167             QRect newPosClip = m_object->getClipRect(x,y);
1168             backgroundRect = backgroundRect.intersect(newPosClip);
1169             foregroundRect = foregroundRect.intersect(newPosClip);
1170         }
1171
1172         // If we establish a clip at all, then go ahead and make sure our background
1173         // rect is intersected with our layer's bounds.
1174         backgroundRect = backgroundRect.intersect(layerBounds);
1175     }
1176 }
1177
1178 static bool mustExamineRenderer(RenderObject* renderer)
1179 {
1180     if (renderer->isCanvas() || renderer->isRoot() || renderer->isInlineFlow())
1181         return true;
1182     
1183     QRect bbox = renderer->borderBox();
1184     QRect overflowRect = renderer->overflowRect(false);
1185     if (bbox != overflowRect)
1186         return true;
1187     QRect floatRect = renderer->floatRect();
1188     if (bbox != floatRect)
1189         return true;
1190
1191     return false;
1192 }
1193
1194 bool RenderLayer::intersectsDamageRect(const QRect& layerBounds, const QRect& damageRect) const
1195 {
1196     return mustExamineRenderer(renderer()) || layerBounds.intersects(damageRect);
1197 }
1198
1199 bool RenderLayer::containsPoint(int x, int y, const QRect& damageRect) const
1200 {
1201     return mustExamineRenderer(renderer()) || damageRect.contains(x, y);
1202 }
1203
1204 void RenderLayer::clearClipRects()
1205 {
1206     if (!m_clipRects)
1207         return;
1208
1209     clearClipRect();
1210     
1211     for (RenderLayer* l = firstChild(); l; l = l->nextSibling())
1212         l->clearClipRects();
1213 }
1214
1215 void RenderLayer::clearClipRect()
1216 {
1217     if (m_clipRects) {
1218         m_clipRects->deref(m_object->renderArena());
1219         m_clipRects = 0;
1220     }
1221 }
1222
1223 // This code has been written to anticipate the addition of CSS3-::outside and ::inside generated
1224 // content (and perhaps XBL).  That's why it uses the render tree and not the DOM tree.
1225 static RenderObject* hoverAncestor(RenderObject* obj)
1226 {
1227     return (!obj->isInline() && obj->continuation()) ? obj->continuation() : obj->parent();
1228 }
1229
1230 static RenderObject* commonAncestor(RenderObject* obj1, RenderObject* obj2)
1231 {
1232     if (!obj1 || !obj2)
1233         return 0;
1234
1235     for (RenderObject* currObj1 = obj1; currObj1; currObj1 = hoverAncestor(currObj1))
1236         for (RenderObject* currObj2 = obj2; currObj2; currObj2 = hoverAncestor(currObj2))
1237             if (currObj1 == currObj2)
1238                 return currObj1;
1239
1240     return 0;
1241 }
1242
1243 void RenderLayer::updateHoverActiveState(RenderObject::NodeInfo& info)
1244 {
1245     // We don't update :hover/:active state when the info is marked as readonly.
1246     if (info.readonly())
1247         return;
1248
1249     // Check to see if the hovered node has changed.  If not, then we don't need to
1250     // do anything.  An exception is if we just went from :hover into :hover:active,
1251     // in which case we need to update to get the new :active state.
1252     DOM::DocumentImpl* doc = renderer()->document();
1253     DOM::NodeImpl* oldHoverNode = doc ? doc->hoverNode() : 0;
1254     DOM::NodeImpl* newHoverNode = info.innerNode();
1255
1256     // Update our current hover node.
1257     if (doc)
1258         doc->setHoverNode(newHoverNode);
1259
1260     // We have two different objects.  Fetch their renderers.
1261     RenderObject* oldHoverObj = oldHoverNode ? oldHoverNode->renderer() : 0;
1262     RenderObject* newHoverObj = newHoverNode ? newHoverNode->renderer() : 0;
1263     
1264     // Locate the common ancestor render object for the two renderers.
1265     RenderObject* ancestor = commonAncestor(oldHoverObj, newHoverObj);
1266     
1267     if (oldHoverObj != newHoverObj) {
1268         // The old hover path only needs to be cleared up to (and not including) the common ancestor;
1269         for (RenderObject* curr = oldHoverObj; curr && curr != ancestor; curr = hoverAncestor(curr)) {
1270             curr->setMouseInside(false);
1271             if (curr->element() && !curr->isText()) {
1272                 bool oldActive = curr->element()->active();
1273                 curr->element()->setActive(false);
1274                 if (curr->style()->affectedByHoverRules() ||
1275                     (curr->style()->affectedByActiveRules() && oldActive))
1276                     curr->element()->setChanged();
1277             }
1278         }
1279     }
1280
1281     // Now set the hover state for our new object up to the root.
1282     for (RenderObject* curr = newHoverObj; curr; curr = hoverAncestor(curr)) {
1283         bool oldInside = curr->mouseInside();
1284         curr->setMouseInside(true);
1285         if (curr->element() && !curr->isText()) {
1286             bool oldActive = curr->element()->active();
1287             curr->element()->setActive(info.active());
1288             if ((curr->style()->affectedByHoverRules() && !oldInside) ||
1289                 (curr->style()->affectedByActiveRules() && oldActive != info.active()))
1290                 curr->element()->setChanged();
1291         }
1292     }
1293 }
1294
1295 // Sort the buffer from lowest z-index to highest.  The common scenario will have
1296 // most z-indices equal, so we optimize for that case (i.e., the list will be mostly
1297 // sorted already).
1298 static void sortByZOrder(QPtrVector<RenderLayer>* buffer,
1299                          QPtrVector<RenderLayer>* mergeBuffer,
1300                          uint start, uint end)
1301 {
1302     if (start >= end)
1303         return; // Sanity check.
1304
1305     if (end - start <= 6) {
1306         // Apply a bubble sort for smaller lists.
1307         for (uint i = end-1; i > start; i--) {
1308             bool sorted = true;
1309             for (uint j = start; j < i; j++) {
1310                 RenderLayer* elt = buffer->at(j);
1311                 RenderLayer* elt2 = buffer->at(j+1);
1312                 if (elt->zIndex() > elt2->zIndex()) {
1313                     sorted = false;
1314                     buffer->insert(j, elt2);
1315                     buffer->insert(j+1, elt);
1316                 }
1317             }
1318             if (sorted)
1319                 return;
1320         }
1321     }
1322     else {
1323         // Peform a merge sort for larger lists.
1324         uint mid = (start+end)/2;
1325         sortByZOrder(buffer, mergeBuffer, start, mid);
1326         sortByZOrder(buffer, mergeBuffer, mid, end);
1327
1328         RenderLayer* elt = buffer->at(mid-1);
1329         RenderLayer* elt2 = buffer->at(mid);
1330
1331         // Handle the fast common case (of equal z-indices).  The list may already
1332         // be completely sorted.
1333         if (elt->zIndex() <= elt2->zIndex())
1334             return;
1335
1336         // We have to merge sort.  Ensure our merge buffer is big enough to hold
1337         // all the items.
1338         mergeBuffer->resize(end - start);
1339         uint i1 = start;
1340         uint i2 = mid;
1341
1342         elt = buffer->at(i1);
1343         elt2 = buffer->at(i2);
1344
1345         while (i1 < mid || i2 < end) {
1346             if (i1 < mid && (i2 == end || elt->zIndex() <= elt2->zIndex())) {
1347                 mergeBuffer->insert(mergeBuffer->count(), elt);
1348                 i1++;
1349                 if (i1 < mid)
1350                     elt = buffer->at(i1);
1351             }
1352             else {
1353                 mergeBuffer->insert(mergeBuffer->count(), elt2);
1354                 i2++;
1355                 if (i2 < end)
1356                     elt2 = buffer->at(i2);
1357             }
1358         }
1359
1360         for (uint i = start; i < end; i++)
1361             buffer->insert(i, mergeBuffer->at(i-start));
1362
1363         mergeBuffer->clear();
1364     }
1365 }
1366
1367 void RenderLayer::dirtyZOrderLists()
1368 {
1369     if (m_posZOrderList)
1370         m_posZOrderList->clear();
1371     if (m_negZOrderList)
1372         m_negZOrderList->clear();
1373     m_zOrderListsDirty = true;
1374 }
1375     
1376 void RenderLayer::updateZOrderLists()
1377 {
1378     if (!isStackingContext() || !m_zOrderListsDirty)
1379         return;
1380     
1381     for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
1382         child->collectLayers(m_posZOrderList, m_negZOrderList);
1383
1384     // Sort the two lists.
1385     if (m_posZOrderList) {
1386         QPtrVector<RenderLayer> mergeBuffer;
1387         sortByZOrder(m_posZOrderList, &mergeBuffer, 0, m_posZOrderList->count());
1388     }
1389     if (m_negZOrderList) {
1390         QPtrVector<RenderLayer> mergeBuffer;
1391         sortByZOrder(m_negZOrderList, &mergeBuffer, 0, m_negZOrderList->count());
1392     }
1393
1394     m_zOrderListsDirty = false;
1395 }
1396
1397 void RenderLayer::collectLayers(QPtrVector<RenderLayer>*& posBuffer, QPtrVector<RenderLayer>*& negBuffer)
1398 {
1399     // FIXME: A child render object or layer could override visibility.  Don't remove this
1400     // optimization though until RenderObject's nodeAtPoint is patched to understand what to do
1401     // when visibility is overridden by a child.
1402     if (renderer()->style()->visibility() != VISIBLE)
1403         return;
1404     
1405     // Determine which buffer the child should be in.
1406     QPtrVector<RenderLayer>*& buffer = (zIndex() >= 0) ? posBuffer : negBuffer;
1407
1408     // Create the buffer if it doesn't exist yet.
1409     if (!buffer)
1410         buffer = new QPtrVector<RenderLayer>();
1411     
1412     // Resize by a power of 2 when our buffer fills up.
1413     if (buffer->count() == buffer->size())
1414         buffer->resize(2*(buffer->size()+1));
1415
1416     // Append ourselves at the end of the appropriate buffer.
1417     buffer->insert(buffer->count(), this);
1418
1419     // Recur into our children to collect more layers, but only if we don't establish
1420     // a stacking context.
1421     if (!isStackingContext()) {
1422         for (RenderLayer* child = firstChild(); child; child = child->nextSibling())
1423             child->collectLayers(posBuffer, negBuffer);
1424     }
1425 }
1426
1427 void RenderLayer::repaintIncludingDescendants()
1428 {
1429     m_object->repaint();
1430     for (RenderLayer* curr = firstChild(); curr; curr = curr->nextSibling())
1431         curr->repaintIncludingDescendants();
1432 }
1433
1434 void RenderLayer::styleChanged()
1435 {
1436     if (m_object->style()->overflow() == OMARQUEE && m_object->style()->marqueeBehavior() != MNONE) {
1437         if (!m_marquee)
1438             m_marquee = new Marquee(this);
1439         m_marquee->updateMarqueeStyle();
1440     }
1441     else if (m_marquee) {
1442         delete m_marquee;
1443         m_marquee = 0;
1444     }
1445 }
1446
1447 void RenderLayer::suspendMarquees()
1448 {
1449     if (m_marquee)
1450         m_marquee->suspend();
1451     
1452     for (RenderLayer* curr = firstChild(); curr; curr = curr->nextSibling())
1453         curr->suspendMarquees();
1454 }
1455
1456 // --------------------------------------------------------------------------
1457 // Marquee implementation
1458
1459 Marquee::Marquee(RenderLayer* l)
1460 :m_layer(l), m_currentLoop(0), m_timerId(0), m_start(0), m_end(0), m_speed(0), m_unfurlPos(0), m_reset(false),
1461  m_suspended(false), m_stopped(false), m_whiteSpace(NORMAL), m_direction(MAUTO)
1462 {
1463 }
1464
1465 int Marquee::marqueeSpeed() const
1466 {
1467     int result = m_layer->renderer()->style()->marqueeSpeed();
1468     DOM::NodeImpl* elt = m_layer->renderer()->element();
1469     if (elt && elt->hasTagName(HTMLNames::marquee())) {
1470         HTMLMarqueeElementImpl* marqueeElt = static_cast<HTMLMarqueeElementImpl*>(elt);
1471         result = kMax(result, marqueeElt->minimumDelay());
1472     }
1473     return result;
1474 }
1475
1476 EMarqueeDirection Marquee::direction() const
1477 {
1478     // FIXME: Support the CSS3 "auto" value for determining the direction of the marquee.
1479     // For now just map MAUTO to MBACKWARD
1480     EMarqueeDirection result = m_layer->renderer()->style()->marqueeDirection();
1481     EDirection dir =  m_layer->renderer()->style()->direction();
1482     if (result == MAUTO)
1483         result = MBACKWARD;
1484     if (result == MFORWARD)
1485         result = (dir == LTR) ? MRIGHT : MLEFT;
1486     if (result == MBACKWARD)
1487         result = (dir == LTR) ? MLEFT : MRIGHT;
1488     
1489     // Now we have the real direction.  Next we check to see if the increment is negative.
1490     // If so, then we reverse the direction.
1491     Length increment = m_layer->renderer()->style()->marqueeIncrement();
1492     if (increment.value < 0)
1493         result = static_cast<EMarqueeDirection>(-result);
1494     
1495     return result;
1496 }
1497
1498 bool Marquee::isHorizontal() const
1499 {
1500     return direction() == MLEFT || direction() == MRIGHT;
1501 }
1502
1503 bool Marquee::isUnfurlMarquee() const
1504 {
1505     EMarqueeBehavior behavior = m_layer->renderer()->style()->marqueeBehavior();
1506     return (behavior == MUNFURL);
1507 }
1508
1509 int Marquee::computePosition(EMarqueeDirection dir, bool stopAtContentEdge)
1510 {
1511     RenderObject* o = m_layer->renderer();
1512     RenderStyle* s = o->style();
1513     if (isHorizontal()) {
1514         bool ltr = s->direction() == LTR;
1515         int clientWidth = o->clientWidth();
1516         int contentWidth = ltr ? o->rightmostPosition(true, false) : o->leftmostPosition(true, false);
1517         if (ltr)
1518             contentWidth += (o->paddingRight() - o->borderLeft());
1519         else {
1520             contentWidth = o->width() - contentWidth;
1521             contentWidth += (o->paddingLeft() - o->borderRight());
1522         }
1523         if (dir == MRIGHT) {
1524             if (stopAtContentEdge)
1525                 return kMax(0, ltr ? (contentWidth - clientWidth) : (clientWidth - contentWidth));
1526             else
1527                 return ltr ? contentWidth : clientWidth;
1528         }
1529         else {
1530             if (stopAtContentEdge)
1531                 return kMin(0, ltr ? (contentWidth - clientWidth) : (clientWidth - contentWidth));
1532             else
1533                 return ltr ? -clientWidth : -contentWidth;
1534         }
1535     }
1536     else {
1537         int contentHeight = m_layer->renderer()->lowestPosition(true, false) - 
1538                             m_layer->renderer()->borderTop() + m_layer->renderer()->paddingBottom();
1539         int clientHeight = m_layer->renderer()->clientHeight();
1540         if (dir == MUP) {
1541             if (stopAtContentEdge)
1542                  return kMin(contentHeight - clientHeight, 0);
1543             else
1544                 return -clientHeight;
1545         }
1546         else {
1547             if (stopAtContentEdge)
1548                 return kMax(contentHeight - clientHeight, 0);
1549             else 
1550                 return contentHeight;
1551         }
1552     }    
1553 }
1554
1555 void Marquee::start()
1556 {
1557     if (m_timerId || m_layer->renderer()->style()->marqueeIncrement().value == 0)
1558         return;
1559     
1560     if (!m_suspended && !m_stopped) {
1561         if (isUnfurlMarquee()) {
1562             bool forward = direction() == MDOWN || direction() == MRIGHT;
1563             bool isReversed = (forward && m_currentLoop % 2) || (!forward && !(m_currentLoop % 2));
1564             m_unfurlPos = isReversed ? m_end : m_start;
1565             m_layer->renderer()->setChildNeedsLayout(true);
1566         }
1567         else {
1568             if (isHorizontal())
1569                 m_layer->scrollToOffset(m_start, 0, false, false);
1570             else
1571                 m_layer->scrollToOffset(0, m_start, false, false);
1572         }
1573     }
1574     else {
1575         m_suspended = false;
1576         m_stopped = false;
1577     }
1578
1579     m_timerId = startTimer(speed());
1580 }
1581
1582 void Marquee::suspend()
1583 {
1584     if (m_timerId) {
1585         killTimer(m_timerId);
1586         m_timerId = 0;
1587     }
1588     
1589     m_suspended = true;
1590 }
1591
1592 void Marquee::stop()
1593 {
1594     if (m_timerId) {
1595         killTimer(m_timerId);
1596         m_timerId = 0;
1597     }
1598     
1599     m_stopped = true;
1600 }
1601
1602 void Marquee::updateMarqueePosition()
1603 {
1604     bool activate = (m_totalLoops <= 0 || m_currentLoop < m_totalLoops);
1605     if (activate) {
1606         if (isUnfurlMarquee()) {
1607             if (m_unfurlPos < m_start) {
1608                 m_unfurlPos = m_start;
1609                 m_layer->renderer()->setChildNeedsLayout(true);
1610             }
1611             else if (m_unfurlPos > m_end) {
1612                 m_unfurlPos = m_end;
1613                 m_layer->renderer()->setChildNeedsLayout(true);
1614             }
1615         }
1616         else {
1617             EMarqueeBehavior behavior = m_layer->renderer()->style()->marqueeBehavior();
1618             m_start = computePosition(direction(), behavior == MALTERNATE);
1619             m_end = computePosition(reverseDirection(), behavior == MALTERNATE || behavior == MSLIDE);
1620         }
1621         if (!m_stopped)
1622             start();
1623     }
1624 }
1625
1626 void Marquee::updateMarqueeStyle()
1627 {
1628     RenderStyle* s = m_layer->renderer()->style();
1629     
1630     if (m_direction != s->marqueeDirection() || (m_totalLoops != s->marqueeLoopCount() && m_currentLoop >= m_totalLoops))
1631         m_currentLoop = 0; // When direction changes or our loopCount is a smaller number than our current loop, reset our loop.
1632     
1633     m_totalLoops = s->marqueeLoopCount();
1634     m_direction = s->marqueeDirection();
1635     m_whiteSpace = s->whiteSpace();
1636     
1637     if (m_layer->renderer()->isHTMLMarquee()) {
1638         // Hack for WinIE.  In WinIE, a value of 0 or lower for the loop count for SLIDE means to only do
1639         // one loop.
1640         if (m_totalLoops <= 0 && (s->marqueeBehavior() == MSLIDE || s->marqueeBehavior() == MUNFURL))
1641             m_totalLoops = 1;
1642         
1643         // Hack alert: Set the white-space value to nowrap for horizontal marquees with inline children, thus ensuring
1644         // all the text ends up on one line by default.  Limit this hack to the <marquee> element to emulate
1645         // WinIE's behavior.  Someone using CSS3 can use white-space: nowrap on their own to get this effect.
1646         // Second hack alert: Set the text-align back to auto.  WinIE completely ignores text-align on the
1647         // marquee element.
1648         // FIXME: Bring these up with the CSS WG.
1649         if (isHorizontal() && m_layer->renderer()->childrenInline()) {
1650             s->setWhiteSpace(NOWRAP);
1651             s->setTextAlign(TAAUTO);
1652         }
1653     }
1654     
1655     //Marquee height hack!! Make sure that, if it is a horizontal marquee, the height attribute is overridden 
1656     //if it is smaller than the font size. If it is a vertical marquee and height is not specified, we default
1657     //to a marquee of 200px.
1658     if (isHorizontal()) {
1659         if (s->height().isFixed() && (s->height().value < s->fontSize())) 
1660             s->setHeight(Length(s->fontSize(),Fixed));
1661     } else if (s->height().isVariable())  //vertical marquee with no specified height
1662         s->setHeight(Length(200,Fixed)); 
1663    
1664     if (speed() != marqueeSpeed()) {
1665         m_speed = marqueeSpeed();
1666         if (m_timerId) {
1667             killTimer(m_timerId);
1668             m_timerId = startTimer(speed());
1669         }
1670     }
1671     
1672     // Check the loop count to see if we should now stop.
1673     bool activate = (m_totalLoops <= 0 || m_currentLoop < m_totalLoops);
1674     if (activate && !m_timerId)
1675         m_layer->renderer()->setNeedsLayout(true);
1676     else if (!activate && m_timerId) {
1677         // Destroy the timer.
1678         killTimer(m_timerId);
1679         m_timerId = 0;
1680     }
1681 }
1682
1683 void Marquee::timerEvent(QTimerEvent* evt)
1684 {
1685     if (m_layer->renderer()->needsLayout())
1686         return;
1687     
1688     if (m_reset) {
1689         m_reset = false;
1690         if (isHorizontal())
1691             m_layer->scrollToXOffset(m_start);
1692         else
1693             m_layer->scrollToYOffset(m_start);
1694         return;
1695     }
1696     
1697     RenderStyle* s = m_layer->renderer()->style();
1698     
1699     int endPoint = m_end;
1700     int range = m_end - m_start;
1701     int newPos;
1702     if (range == 0)
1703         newPos = m_end;
1704     else {  
1705         bool addIncrement = direction() == MUP || direction() == MLEFT;
1706         bool isReversed = s->marqueeBehavior() == MALTERNATE && m_currentLoop % 2;
1707         if (isUnfurlMarquee()) {
1708             isReversed = (!addIncrement && m_currentLoop % 2) || (addIncrement && !(m_currentLoop % 2));
1709             addIncrement = !isReversed;
1710         }
1711         if (isReversed) {
1712             // We're going in the reverse direction.
1713             endPoint = m_start;
1714             range = -range;
1715             if (!isUnfurlMarquee())
1716                 addIncrement = !addIncrement;
1717         }
1718         bool positive = range > 0;
1719         int clientSize = isUnfurlMarquee() ? abs(range) :
1720             (isHorizontal() ? m_layer->renderer()->clientWidth() : m_layer->renderer()->clientHeight());
1721         int increment = kMax(1, abs(m_layer->renderer()->style()->marqueeIncrement().width(clientSize)));
1722         int currentPos = isUnfurlMarquee() ? m_unfurlPos : 
1723             (isHorizontal() ? m_layer->scrollXOffset() : m_layer->scrollYOffset());
1724         newPos =  currentPos + (addIncrement ? increment : -increment);
1725         if (positive)
1726             newPos = kMin(newPos, endPoint);
1727         else
1728             newPos = kMax(newPos, endPoint);
1729     }
1730
1731     if (newPos == endPoint) {
1732         m_currentLoop++;
1733         if (m_totalLoops > 0 && m_currentLoop >= m_totalLoops) {
1734             killTimer(m_timerId);
1735             m_timerId = 0;
1736         }
1737         else if (s->marqueeBehavior() != MALTERNATE && s->marqueeBehavior() != MUNFURL)
1738             m_reset = true;
1739     }
1740     
1741     if (isUnfurlMarquee()) {
1742         m_unfurlPos = newPos;
1743         m_layer->renderer()->setChildNeedsLayout(true);
1744     }
1745     else {
1746         if (isHorizontal())
1747             m_layer->scrollToXOffset(newPos);
1748         else
1749             m_layer->scrollToYOffset(newPos);
1750     }
1751 }
1752