fixes for border-collapsing

[David Hyatt]

The border-collapsing code contains a pretty terrible bug that can 
cause it to build an insane # of borders (making pages hang).  
Basically because css only specifies a partial order rather than a 
total order when comparing borders, the old code was getting confused 
and not recognizing two styles were the same when collecting the unique 
borders.

I also should have used QValueList instead of QPtrList, so I made that 
change too.

You can also see my code here that puts in border collapsing for this 
new PaintInfo struct Dirk added, so you can see how I merged that in.

Two examples of the problem are:

http://californiaracquetball.org/ranking_info.htm (really bad, hangs 
for multiple minutes)
http://www.skating.nf.ca/events_e.htm (not as bad, but should 
scroll/paint/load somewhat sluggishly)

Here's the fix:

-------------- next part --------------
Index: khtml/rendering/render_object.cpp
===================================================================
RCS file: /local/home/cvs/Labyrinth/WebCore/khtml/rendering/render_object.cpp,v
retrieving revision 1.133
diff -u -p -r1.133 khtml/rendering/render_object.cpp
--- khtml/rendering/render_object.cpp	2004/02/23 21:26:26	1.133
+++ khtml/rendering/render_object.cpp	2004/02/23 23:28:49
@@ -2116,7 +2116,7 @@ void RenderObject::updateWidgetPositions
 }
 #endif
 
-void RenderObject::collectBorders(QPtrList<CollapsedBorderValue>& borderStyles)
+void RenderObject::collectBorders(QValueList<CollapsedBorderValue>& borderStyles)
 {
     for (RenderObject* curr = firstChild(); curr; curr = curr->nextSibling())
         curr->collectBorders(borderStyles);
Index: khtml/rendering/render_object.h
===================================================================
RCS file: /local/home/cvs/Labyrinth/WebCore/khtml/rendering/render_object.h,v
retrieving revision 1.105
diff -u -p -r1.105 khtml/rendering/render_object.h
--- khtml/rendering/render_object.h	2004/02/23 21:26:26	1.105
+++ khtml/rendering/render_object.h	2004/02/23 23:28:49
@@ -614,7 +614,7 @@ public:
     virtual void setTable(RenderTable*) {};
 
     // Used by collapsed border tables.
-    virtual void collectBorders(QPtrList<CollapsedBorderValue>& borderStyles);
+    virtual void collectBorders(QValueList<CollapsedBorderValue>& borderStyles);
 
     // Repaint the entire object.  Called when, e.g., the color of a border changes, or when a border
     // style changes.
Index: khtml/rendering/render_table.cpp
===================================================================
RCS file: /local/home/cvs/Labyrinth/WebCore/khtml/rendering/render_table.cpp,v
retrieving revision 1.95
diff -u -p -r1.95 khtml/rendering/render_table.cpp
--- khtml/rendering/render_table.cpp	2004/02/23 21:26:26	1.95
+++ khtml/rendering/render_table.cpp	2004/02/23 23:28:49
@@ -442,18 +442,17 @@ void RenderTable::paint(PaintInfo& i, in
         if (child->isTableSection() || child == tCaption)
 	    child->paint(paintInfo, _tx, _ty);
 
-    if (collapseBorders() && 
-        (paintAction == PaintActionElementBackground || paintAction == PaintActionChildBackground)
-        && style()->visibility() == VISIBLE) {
+    if (collapseBorders() && paintAction == PaintActionChildBackground && style()->visibility() == VISIBLE) {
         // Collect all the unique border styles that we want to paint in a sorted list.  Once we
         // have all the styles sorted, we then do individual passes, painting each style of border
         // from lowest precedence to highest precedence.
-        QPtrList<CollapsedBorderValue> borderStyles;
-        borderStyles.setAutoDelete(true);
-        collectBorders(borderStyles);
         paintInfo.phase = PaintActionCollapsedTableBorders;
-        for (uint i = 0; i < borderStyles.count(); i++) {
-            m_currentBorder = borderStyles.at(i);
+        QValueList<CollapsedBorderValue> borderStyles;
+        collectBorders(borderStyles);
+        QValueListIterator<CollapsedBorderValue> it = borderStyles.begin();
+        QValueListIterator<CollapsedBorderValue> end = borderStyles.end();
+        for (; it != end; ++it) {
+            m_currentBorder = &(*it);
             for (RenderObject* child = firstChild(); child; child = child->nextSibling())
                 if (child->isTableSection())
                     child->paint(paintInfo, _tx, _ty);
@@ -1756,8 +1755,8 @@ void RenderTableCell::setStyle( RenderSt
 // (4) If border styles differ only in color, then a style set on a cell wins over one on a row, 
 // which wins over a row group, column, column group and, lastly, table. It is undefined which color 
 // is used when two elements of the same type disagree.
-static const CollapsedBorderValue compareBorders(const CollapsedBorderValue& border1, 
-                                                 const CollapsedBorderValue& border2)
+static CollapsedBorderValue compareBorders(const CollapsedBorderValue& border1, 
+                                           const CollapsedBorderValue& border2)
 {
     // Sanity check the values passed in.  If either is null, return the other.
     if (!border2.exists()) return border1;
@@ -2069,16 +2068,23 @@ void RenderTableCell::paint(PaintInfo& i
 #endif
 
     _tx += m_x;
-    _ty += m_y + _topExtra;
+    _ty += m_y;
 
     // check if we need to do anything at all...
     int os = 2*maximalOutlineSize(i.phase);
-    if (!overhangingContents() && ((_ty - _topExtra >= i.r.y() + i.r.height() + os)
-                                   || (_ty + m_height + _bottomExtra <= i.r.y() - os))) return;
-    RenderBlock::paintObject(i, _tx, _ty);
+    if (!overhangingContents() && ((_ty >= i.r.y() + i.r.height() + os)
+                                   || (_ty + _topExtra + m_height + _bottomExtra <= i.r.y() - os))) return;
+    
+    if (i.phase == PaintActionCollapsedTableBorders && style()->visibility() == VISIBLE) {
+        int w = width();
+        int h = height() + borderTopExtra() + borderBottomExtra();
+        paintCollapsedBorder(i.p, _tx, _ty, w, h);
+    }
+    else
+        RenderBlock::paintObject(i, _tx, _ty + _topExtra);
 
 #ifdef BOX_DEBUG
-    ::outlineBox( i.p, _tx, _ty - _topExtra, width(), height() + borderTopExtra() + borderBottomExtra());
+    ::outlineBox( i.p, _tx, _ty, width(), height() + borderTopExtra() + borderBottomExtra());
 #endif
 }
 
@@ -2141,31 +2147,25 @@ public:
     int count;
 };
 
-static void addBorderStyle(QPtrList<CollapsedBorderValue>& borderStyles, CollapsedBorderValue borderValue)
+static void addBorderStyle(QValueList<CollapsedBorderValue>& borderStyles, CollapsedBorderValue borderValue)
 {
-    if (!borderValue.exists())
+    if (!borderValue.exists() || borderStyles.contains(borderValue))
         return;
     
-    uint count = borderStyles.count();
-    if (count == 0)
-        borderStyles.append(new CollapsedBorderValue(borderValue));
-    else {
-        for (uint i = 0; i < count; i++) {
-            CollapsedBorderValue* b = borderStyles.at(i);
-            if (*b == borderValue)
-                return;
-            CollapsedBorderValue result = compareBorders(*b, borderValue);
-            if (result == *b) {
-                borderStyles.insert(i, new CollapsedBorderValue(borderValue));
-                return;
-            }
+    QValueListIterator<CollapsedBorderValue> it = borderStyles.begin();
+    QValueListIterator<CollapsedBorderValue> end = borderStyles.end();
+    for (; it != end; ++it) {
+        CollapsedBorderValue result = compareBorders(*it, borderValue);
+        if (result == *it) {
+            borderStyles.insert(it, borderValue);
+            return;
         }
-        
-        borderStyles.append(new CollapsedBorderValue(borderValue));
     }
+
+    borderStyles.append(borderValue);
 }
 
-void RenderTableCell::collectBorders(QPtrList<CollapsedBorderValue>& borderStyles)
+void RenderTableCell::collectBorders(QValueList<CollapsedBorderValue>& borderStyles)
 {
     addBorderStyle(borderStyles, collapsedLeftBorder());
     addBorderStyle(borderStyles, collapsedRightBorder());
Index: khtml/rendering/render_table.h
===================================================================
RCS file: /local/home/cvs/Labyrinth/WebCore/khtml/rendering/render_table.h,v
retrieving revision 1.34
diff -u -p -r1.34 khtml/rendering/render_table.h
--- khtml/rendering/render_table.h	2004/02/11 19:52:38	1.34
+++ khtml/rendering/render_table.h	2004/02/23 23:28:49
@@ -29,7 +29,6 @@
 #define RENDER_TABLE_H
 
 #include <qcolor.h>
-#include <qptrvector.h>
 
 #include "render_box.h"
 #include "render_block.h"
@@ -350,7 +349,7 @@ public:
     CollapsedBorderValue collapsedRightBorder() const;
     CollapsedBorderValue collapsedTopBorder() const;
     CollapsedBorderValue collapsedBottomBorder() const;
-    virtual void collectBorders(QPtrList<CollapsedBorderValue>& borderStyles);
+    virtual void collectBorders(QValueList<CollapsedBorderValue>& borderStyles);
 
     virtual void updateFromElement();
 
-------------- next part --------------