Closed Bug 363329 Opened 18 years ago Closed 18 years ago

[reflow branch] Cell in table with colspan is too wide

Categories

(Core :: Layout: Tables, defect)

Product:
Core
Component:
Layout: Tables
Platform:
x86
Linux
Type:
defect
Priority:
Not set
Severity:
normal

Tracking

()

Status:
RESOLVED FIXED

People

(Reporter: MatsPalmgren_bugz, Assigned: dbaron)

References

(
URL
)

Details

(Keywords: regression, testcase, Whiteboard: [patch])

Attachments

(7 files, 4 obsolete files)

Testcase #1
292 bytes, text/html
Details
slightly enhanced testcase
308 bytes, text/html
Details
testcase from bankisrael.gov
211 bytes, text/html
Details
patch for the cellspacing problem
10.49 KB, patch
dbaron
: review+
dbaron
: superreview+
Details | Diff | Splinter Review
interdiff between the patches
3.24 KB, patch
Details | Diff | Splinter Review
reversed testcase
293 bytes, text/html
Details
patch to accumulate spanning cells grouped by increasing colspan
25.00 KB, patch
Details | Diff | Splinter Review 
Table with colspan is too wide.

Before you dupe this against bug 363150 I should say that it also occurs
in my debug build which has that patch. Sorry, if it's already known
but I thought I should let you know since it's a regression for rather
simple markup.

At the URL you can see the problem when clicking in the navigation menu
on the left.

STEPS TO REPRODUCE
1. load the attached testcase

<table border="1">
  <tr><td colspan="3">Produkte</td></tr>
  <tr><td>&nbsp;</td><td colspan="2">ebuWings</td></tr>
</table>

ACTUAL RESULTS
The first cell in the second row is wider than it used to be before
the reflow branch landing.

EXPECTED RESULT
First cell in 2nd row should be about the width of an "x".
Compare IE7, Opera9, Webkit and Firefox until 2006120701.
Attached file Testcase #1 — 

    
    

    
  


  
There is first a problem of width distribution in condition where the spanned cells have more min-width then the spanning cell, 
then there are two cellspacings on the right hand side, 
third the content overwrites into the cellspacing indicating a min-width cellspacing error.

    
    

    
  
The cellspacing error comes probably from the unconditional substraction of a cellspacing for columns that do not have originating cells
http://lxr.mozilla.org/seamonkey/source/layout/tables/BasicTableLayoutStrategy.cpp#310
vs.
http://lxr.mozilla.org/mozilla1.8/source/layout/tables/BasicTableLayoutStrategy.cpp#766

The too large first column is probably a result of the algorithm
on the first path only the first cell on the second row gives a minimum width to column 0 on the colspan distribution sweep the first cell on the first row needs to distribute its min width, as columns 1 and 2 are empty now (0 widths they do not get any space) http://bonsai.mozilla.org/cvsblame.cgi?file=mozilla/layout/tables/BasicTableLayoutStrategy.cpp&rev=3.236&mark=325,375#318


    
    

    
  


  

    
    

    
  
Based on a very quick look at the patch, the changes to ComputeColumnIntrinsicWidths look wrong since info won't be correct until the last iteration through the loop over spanned columns, but it's used in all iterations.

Also, you probably don't want to leave DEBUG_TABLE_STRATEGY defined, and the stuff inside DEBUG_TABLE_STRATEGY is indented one character too few in some places.

I'm also not a big fan of inserting two blank lines between a comment and the code it's describing.  If you want more separation, I'd rather it be before the comment, although one line after the comment seems ok.

    
    

    
  
You should also remove my comment:
     // XXX Should only add columns that have cells originating in them!

Thanks for fixing that, btw.

    
    

    
  
(In reply to comment #5)
> Based on a very quick look at the patch, the changes to
> ComputeColumnIntrinsicWidths look wrong since info won't be correct until the
> last iteration through the loop over spanned columns, but it's used in all
> iterations.

In other words, I think you need to do what you did in ComputeColumnWidths.

    
    

    
  
Is bug 363437 a dupe of this ?
Blocks: 363437

    
    

    
  
*** Bug 363805 has been marked as a duplicate of this bug. ***

    
    

    
  


  
http://www.bankisrael.gov.il is also broken, /probably/ due to the same issue.
This is a testcase based on that page. the top-left cell should be 100px wide.

    
    

    
  
Bernd, were you planning to update the patch or should I do it?

    
    

    
  
(In reply to comment #10)
> the top-left cell should be 100px wide.

I meant "the top-right cell".

Sorry for the bugspam. 



    
    

    
  
yes, I plan to work on this its only lower priority than recovering from bz's cellmap changes (it causes crash bugs)

    
    

    
  
(In reply to comment #10)
> Created an attachment (id=249028) [edit]
> testcase from bankisrael.gov
> 
> http://www.bankisrael.gov.il is also broken, /probably/ due to the same issue.
> This is a testcase based on that page. the top-left cell should be 100px wide.

The only other browser I can find that makes the top-right cell be 100px wide is Safari.

    
    

    
  
(In reply to comment #5)
> Based on a very quick look at the patch, the changes to
> ComputeColumnIntrinsicWidths look wrong since info won't be correct until the
> last iteration through the loop over spanned columns, but it's used in all
> iterations.

Actually, this case was ok.


I'll take care of updating the patch since it's higher priority for me.

    
    

    
  
The differences between the patches are just:
 * whitespace changes
 * fixing s/#define/#undef/ per comment 5 paragraph 2
 * removing comment per comment 6
 * replacing the addition before the loop to cancel the extra subtraction with a check within the loop for being the first iteration

I'm going to mark this r+sr=dbaron since it's basically just bernd's patch, and go ahead and land it, but feel free to let me know if anything's wrong.
Assignee: nobody → bernd_mozilla

    
    

    
  
Fix checked in to trunk.
Status: NEW → RESOLVED
Closed: 18 years ago
Resolution: --- → FIXED
Blocks: 363144

    
    

    
  
David the patch is fine, but your closure of the bug is premature IMHO. The patch fixed the cellspacing but thats peanuts compared to the reminder which is the colspan width distribution.
Status: RESOLVED → REOPENED
Resolution: FIXED → ---
Assignee: bernd_mozilla → nobody
Status: REOPENED → NEW

    
    

    
  
So, for what it's worth, WinIE has a similar expansion effect if you swap the order of the cells in the row with two cells.

    
    

    
  
The simplest solution I can think of that doesn't violate any nasty invariants that only WinIE violates is to loop through the cells in ComputeColumnIntrinsicWidths in increasing order of colspan, and re-merge the span data into the column data at each colspan increment.

I'm not sure what the right way to optimize that for speed and memory use is, though.  A hashtable of integers seems quite clunky, and all the other obvious solutions seem to have potentially bad memory use or performance in some important cases.

    
    

    
  
Re "The simplest solution...." thats basically what we had before the reflow branch landed. We also had some sort of hashtable for speed optimization.
Assignee: nobody → dbaron

    
    

    
  
(In reply to comment #14)

> The only other browser I can find that makes the top-right cell be 100px wide
> is Safari.
> 

Yes, that's the one I used as a reference (together with a pre-reflow-branch Minefield).

Anyway, I repeated the process, this time with IE7 as a reference, and I ended up with something pretty similar to attachment 248146 [details]. So I'll re-test once this is fixed.


    
    

    
  


  
I'll add the above two examples as reftests (with the reference being the table with the spans decreased by 1).  That's not in the patch because my only tree with clean table code doesn't have a clean reftests directory, so I'll do it as a second step in another tree.

        Attachment #249142 -
        Flags: superreview?(bzbarsky)

        Attachment #249142 -
        Flags: review?(bernd_mozilla)

    
    

    
  
Comment on attachment 249142 [details] [diff] [review]
patch to accumulate spanning cells grouped by increasing colspan (diff -ub)

Works better for bug 363146
For bug 363144 - problem still exists..

        Attachment #249142 -
        Flags: review+

    
    

    
  
I'm not sure I'll be able to get to this before I lose network, or how complete the network loss will be.  So I might not get to this until January...

    
    

    
  
Comment on attachment 249142 [details] [diff] [review]
patch to accumulate spanning cells grouped by increasing colspan (diff -ub)

Whoaa, this is the clearest code that I have seen for ages.

I am not confident that this code does the following:

<tr><td colspan="2" width="400">
<tr><td width ="50"><td>

It should see that the first column is already fix constrained and give all its remaining width 350px to the second column. 

We did that before. 

After a little round of digging I have to admit, that neither IE or Opera do that.

        Attachment #249142 -
        Flags: review?(bernd_mozilla) → review+

    
    

    
  
(In reply to comment #30)
> I am not confident that this code does the following:
> 
> <tr><td colspan="2" width="400">
> <tr><td width ="50"><td>

I didn't do that because I didn't see other browsers doing it.  It does make sense, though, so it's probably worth taking another look; I'd rather have a separate bug for it, though.

In any case, the change to do that would be a little bit above most of my changes, right around the "// ... and actually do the distribution." comment.

        Attachment #249142 -
        Flags: superreview?(bzbarsky) → superreview?(roc)

        Attachment #249142 -
        Flags: superreview?(roc) → superreview?(bzbarsky)
Blocks: 363874

    
    

    
  
*** Bug 363146 has been marked as a duplicate of this bug. ***

    
    

    
  
*** Bug 363437 has been marked as a duplicate of this bug. ***

    
    

    
  
Oops, just noticed that moving the AdjustPrefPercent into a loop that doesn't always execute is incorrect.  I'll fix that in the patch on bug 363874.

    
    

    
  
Comment on attachment 249039 [details] [diff] [review]
patch for the cellspacing problem 

>+    for (PRInt32 col = 0; col < colCount; ++col) {
Note that this broke portability rule #20, although I guess this only breaks VC6.
http://www.mozilla.org/hacking/portable-cpp.html#variables_in_for

    
    

    
  
So I'm trying to understand what the net effect of the change is.  What does the sort actually do for us?

    
    

    
  
The way we achieve invariance under reordering of rows, while processing spanning cells, was (in the old code) to accumulate the amount of extra space needed for each cell given the widths the columns would have considering only non-spanning cells, and distributing that space among the spanned columns.  Each column would then get the largest of such distributions, all computed relative to the column widths computed only from non-spanning cells.

What we're doing with the patch is doing that process separately for each number of columns spanned, so rather than doing non-spanning cells and then spanning cells, we're considering non-spanning cells, then distributing the excess needed for cells with colspan 2 (but the maximum excess relative to the non-spanning cells), then distributing the excess needed for cells with colspan 3 relative to the column widths including the non-spanning cells and the distributions of widths from cells with colspan 2, etc.

    
    

    
  
(This also gives invariance under reordering of columns, except for the case of percentage widths that add to more than 100%, in which browser behavior quite interoperably varies under column reordering.)

    
    

    
  
Ah, ok.  Might be worth putting some version of this text in the patch....

I'll try to read the patch in detail on Thursday.
Blocks: 352461

    
    

    
  
Comment on attachment 249142 [details] [diff] [review]
patch to accumulate spanning cells grouped by increasing colspan (diff -ub)

>Index: SpanningCellSorter.h

Can we add a privately declared operator new (not implemented) to make sure no one heap-allocates this?

>+    enum State { ADDING, ENUMERATING_ARRAY, ENUMERATING_HASH, DONE };

Maybe document these?  They're pretty clear, I guess...

>+    PR_STATIC_CALLBACK(PLDHashOperator)
>+        FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
>+                        PRUint32 number, void *arg);

Document what this will expect to be passed in as the |arg|?

>+    static int SortArray(const void *a, const void *b, void *closure);

Same for the args to this method?

>Index: SpanningCellSorter.cpp
>+    mPresShell->PushStackMemory();

So... this can return OOM.  Though given that StackArena::StackArena allocates stuff and doesn't propagate OOM, I guess that's ok...  Maybe just file a followup to make this code deal with allocation failures?

>+SpanningCellSorter::AddCell(PRInt32 aColSpan, PRInt32 aRow, PRInt32 aCol)
>+        NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
>+                     "wrong entry");

Can you assert that |(entry->mColSpan == 0) == (entry->mItems == nsnull)|?

>+SpanningCellSorter::GetNext()
>+                HashTableEntry **sh =
>+                    new HashTableEntry*[mHashTable.entryCount];

Should we worry about OOM here?

>Index: BasicTableLayoutStrategy.cpp
>BasicTableLayoutStrategy::ComputeColumnIntrinsicWidths(nsIRenderingContext* aRenderingContext)
>+            if (colSpan > 1) {
>+                spanningCells.AddCell(colSpan, row, col);
>+                continue;

So... Computing that colSpan is not that cheap (and for cells with large colspans can actually be pathologically expensive).  What do you think about having GetNext() return a struct that has the colspan and the Item* or put the colspan into an out param or whatever, since the SpanningCellSorter knows that information anyway?

>+    while ((item = spanningCells.GetNext())) {

The comment right before this line is about where it seems like comment 37 should go.

>             nsTableCellFrame *cellFrame =
>                 cellMap->GetCellInfoAt(row, col, &originates, &colSpan);

If GetNext() returned the colspan, here you could use:

  cellMap->GetDataAt(row, col)->GetCellFrame();

since you'd know the colspan from the call to GetNext() and you'd know there's an originating data at those coords.  If desired, this could be split up over two lines so you can assert that GetDataAt() returns a non-null CellData that's IsOrig().

sr=bzbarsky with those addressed.

        Attachment #249142 -
        Flags: superreview?(bzbarsky) → superreview+

    
    

    
  
(In reply to comment #40)
> (From update of attachment 249142 [details] [diff] [review])
> >Index: SpanningCellSorter.h
> 
> Can we add a privately declared operator new (not implemented) to make sure no
> one heap-allocates this?

Is there a particular problem with allocating it on the heap?  The hash table is probably going to be considerably bigger than the internal array.

> >+    enum State { ADDING, ENUMERATING_ARRAY, ENUMERATING_HASH, DONE };
> 
> Maybe document these?  They're pretty clear, I guess...

I prefer self-documenting code to documentation, since it has less of a tendency to get out of date.  I think they're clear enough.

> >+    PR_STATIC_CALLBACK(PLDHashOperator)
> >+        FillSortedArray(PLDHashTable *table, PLDHashEntryHdr *hdr,
> >+                        PRUint32 number, void *arg);
> 
> Document what this will expect to be passed in as the |arg|?
> 
> >+    static int SortArray(const void *a, const void *b, void *closure);
> 
> Same for the args to this method?

These are both methods that, in a sensible language, would be defined as nested functions right where they are used.  They're no more generic than that, and it's pretty clear that that's what they are.  I'd make them file-static instead of class-static, but then I'd have to do friend stuff or move types out of the class as well.

> >Index: SpanningCellSorter.cpp
> >+    mPresShell->PushStackMemory();
> 
> So... this can return OOM.  Though given that StackArena::StackArena allocates
> stuff and doesn't propagate OOM, I guess that's ok...  Maybe just file a
> followup to make this code deal with allocation failures?

Frankly, I don't think PushStackMemory should propagate OOM; it has no need to.  If we can't create the stack arena, then AllocateStackMemory will also fail, and that we should check.  If we fail to create the stack arena at push time but can create it at allocate time, we'll have an extra pop, which shouldn't be harmful (but currently is).  So I think I should leave this as-is and file a followup bug to:
 (1) make StackArena::Pop deal more gracefully with an extra pop.
 (2) make PushStackMemory and PopStackMemory never fail

> >+SpanningCellSorter::AddCell(PRInt32 aColSpan, PRInt32 aRow, PRInt32 aCol)
> >+        NS_ASSERTION(entry->mColSpan == 0 || entry->mColSpan == aColSpan,
> >+                     "wrong entry");
> 
> Can you assert that |(entry->mColSpan == 0) == (entry->mItems == nsnull)|?

Done.

> >+SpanningCellSorter::GetNext()
> >+                HashTableEntry **sh =
> >+                    new HashTableEntry*[mHashTable.entryCount];
> 
> Should we worry about OOM here?

I just decided to set state to DONE return early.  I'm not worried about bad layout on OOM.

> >Index: BasicTableLayoutStrategy.cpp
> >BasicTableLayoutStrategy::ComputeColumnIntrinsicWidths(nsIRenderingContext* aRenderingContext)
> >+            if (colSpan > 1) {
> >+                spanningCells.AddCell(colSpan, row, col);
> >+                continue;
> 
> So... Computing that colSpan is not that cheap (and for cells with large
> colspans can actually be pathologically expensive).  What do you think about

I don't see why it should ever need to be expensive for an originating cell, nor do I understand what GetCellInfoAt even means for cases of overlap.

> having GetNext() return a struct that has the colspan and the Item* or put the
> colspan into an out param or whatever, since the SpanningCellSorter knows that
> information anyway?
...
> >             nsTableCellFrame *cellFrame =
> >                 cellMap->GetCellInfoAt(row, col, &originates, &colSpan);
> 
> If GetNext() returned the colspan, here you could use:
> 
>   cellMap->GetDataAt(row, col)->GetCellFrame();
> 
> since you'd know the colspan from the call to GetNext() and you'd know there's
> an originating data at those coords.  If desired, this could be split up over
> two lines so you can assert that GetDataAt() returns a non-null CellData that's
> IsOrig().

But I'll do this anyway, although I'll make aColSpan be an out parameter.

> >+    while ((item = spanningCells.GetNext())) {
> 
> The comment right before this line is about where it seems like comment 37
> should go.

Will do.

I'm also going to roll in the fix in comment 34 that was previously part of the patch to bug 363144.

    
    

    
  
> Is there a particular problem with allocating it on the heap?

Not as long as it's destroyed promptly.  Otherwise, the stack memory thing could cause issues.

> So I think I should leave this as-is and file a followup bug 

Sounds good.

> I don't see why it should ever need to be expensive for an originating cell,

The problem is that it's computing an effective colspan, not just looking at the colspan attribute.  Which means that it iterates along the row the cell is in until it hits a CellData that's not IsColSpan().  So if I have colspan="1000", we'll look at 1000 CellDatas.

In that last patch, I'd switch the order of these two lines:

+            nsTableCellFrame *cellFrame = cellData->GetCellFrame();
+            NS_ASSERTION(cellData && cellData->IsOrig(),
+                         "bogus result from spanning cell sorter");



    
    

    
  
> > So I think I should leave this as-is and file a followup bug 
> 
> Sounds good.

Filed bug 366866.
No longer depends on: 366865

    
    

    
  
Fix checked in to trunk, 2007-01-12 17:04 PST (-0800, America/Los_Angeles).
Status: NEW → RESOLVED
Closed: 18 years ago → 18 years ago
Resolution: --- → FIXED

          You need to log in
          before you can comment on or make changes to this bug.
        






  

    
  







  

    

      
Attachment

      

      
      
      
      
    

    

      

        

          

            
General

            

              Creator: 



            

            
Created: 

            
Updated: 

            
Size: