Infinite loop in multi-column layout after first (page-)break-before #1020

LukasKlement · 2020-01-04T14:04:34Z

Using WeasyPrint==51, in a 2-column layout, write_pdf() causes an infinite loop when (page-)break-before: always; is applied to more than 1 block:

<!DOCTYPE html>
<html>
  <head>
    <style type="text/css">
      .content {
        columns: 2;
      }

      .page-break {
        break-before: always;
      }
    </style>
  </head>

  <body>
    <div class="content">
      <div>Page 1, column 1</div>
      <div class="page-break">Page 1, column 2</div>
      <div class="page-break">Page 2, column 1</div>
    </div>
  </body>
</html>

The same error happens for versions 48, 49 and 50. WeasyPrint==47 works fine. Leaving the second page-break block away, the pdf renders.

The text was updated successfully, but these errors were encountered:

grewn0uille · 2020-01-06T15:29:49Z

Seems to be broken by adb5216

LukasKlement · 2021-08-12T06:53:43Z

Update for v53: the issue is still current: v53 is still unusable when it comes to multi-column block layouts.
WeasyPrint==47 is the last version without this infinite loop.

Edit:
The bug is still current for versions 54 and 54.1

drboone · 2022-02-11T21:40:30Z

I seem to have this issue too. It may be somewhat content-dependent. Our layout uses CSS-implied tables:

.row
{
    display: table;
}
.col
{
    float: left;
}

When the loop occurs, weasyprint uses 100% of a cpu core, and ram utilization climbs slowly but steadily. After about 20 minutes, the current example is over 1 GB. v53.4.

I can assemble the current document as an example for a developer, but can't really share it publicly.

drboone · 2022-02-18T17:06:25Z

I've supplied a reproducer to liZe.

drboone · 2022-03-03T00:06:07Z

Are people actually seeing the comments on this issue?

aschmitz · 2022-03-03T04:44:06Z

Going back from this comment, I see three comments from you, then a cross-reference from issue 1549.

Are you seeing an actual infinite loop, or is it "just" that multi-column layouts take an excruciatingly long time to render? I have a local test document (which I unfortunately can't share, although I could probably mock up something if necessary) composed primarily of an extremely long list that took about 41 minutes to render inside a column-count: 3 div, but took about a minute and a half without the wrapper. (The list was about 400 pages in one column, and about a third the length in three columns.)

I have some profiling from each render, so if I get a chance I'll try to dig into it, but it would be good to nail down exactly what's happening, as I haven't necessary run into it as a display: table / float: left issue.

drboone · 2022-03-03T06:38:24Z

Well, I know I had given my reproducer at least 20 minutes once, and it's nowhere near as big as yours. I've been watching another trial run for over 90 minutes and it hasn't finished yet, and RAM utilization is up to 3.4 GB. It should come out to be a little less than 50 pages. It is a series of letters, and in effect a two-column layout, with letterhead stuff left, and body right. Only a few of the letters run to a second page.

LukasKlement · 2022-03-03T08:50:32Z

To add to the initial bug report: indeed, these 20 lines of HTML/CSS lead to 100% CPU utilization and ever-increasing RAM usage.

drboone · 2022-03-03T16:58:59Z

I was curious, so I left this running. After 12 hours of 100% cpu use, it still hasn't finished, but is using nearly 9.5 GB of RAM.

But I'm pretty sure that solving this particular halting problem is less relevant than the fact that it's completely impractical if it takes even multiple minutes to render. :)

aschmitz · 2022-03-04T05:23:42Z

Yep, the reproducer at the top of this issue is indeed an infinite loop. You end up looping in here:

WeasyPrint/weasyprint/layout/column.py

Lines 149 to 162 in e17e536

    
           while True: 
        
               # Remove extra excluded shapes introduced during previous loop 
        
               new_excluded_shapes = ( 
        
                   len(context.excluded_shapes) - len(excluded_shapes)) 
        
               for i in range(new_excluded_shapes): 
        
                   context.excluded_shapes.pop() 
        
               for i in range(count): 
        
                   # Render the column 
        
                   new_box, resume_at, next_page, _, _ = block_box_layout( 
        
                       context, column_box, 
        
                       context.page_bottom - current_position_y - height, 
        
                       column_skip_stack, containing_block, page_is_empty, 
        
                       [], [], [], discard=False)

Effectively, this loop is trying to increase the height of the columns until everything fits between the two columns. It's failing because it will never fit all three required columns into two columns.

An easy resolution would be to pop an additional condition in line 209 and 212:

WeasyPrint/weasyprint/layout/column.py

Lines 209 to 213 in e17e536

    
               if resume_at is None: 
        
                   break 
        
           if column_skip_stack is None: 
        
               # We rendered the whole content, stop

We could add or next_page['break'] != 'any' to the condition and escape this loop (because next_page has break set to page (or some other page specifier) rather than any when it must break), but it's not clear that doing so is really correct. In particular, if you were to double the "Page 1, column 1" div, you'd end up with one copy on each of the first two columns, then the forced break would go onto the next column (page 2, column 1).

I'd have to think for a while on what a good way to resolve that is: perhaps there's some way to make a last-ditch attempt to heighten the remaining columns if we'd have to break pages? @liZe may (hopefully will!) have better ideas.

Because that loop is in the column code, though, I don't think it's the cause of the issue you're running into, @drboone. Is there any chance you can try deleting chunks of your HTML + CSS until it works, and then re-add whatever was last to get it to a more minimal (and ideally, sharable) state? I'm not a maintainer, but I've been digging into some performance issues we've been running into at work and might be able to help triage things.

aschmitz · 2022-03-04T06:37:40Z

Okay, for columns, I think the following might work:

Try typesetting with the full remaining height on the page. If everything doesn't fit, either because there is too much content or because a page break was forced, we are done, the columns should be that height.
If everything did fit, average the heights of the columns, use that as the new height, and proceed as we currently do to try bumping up the height to fit everything, since we know it will inevitably fit.

I suspect that would also resolve the very long render times I saw with an extremely long multi-column document, as it won't default to slowly expanding and re-layouting every potential height. There's a minor risk of an extra pass if everything would have fit in the first column layout attempted in the current code, but that seems somewhat unlikely in general column usage.

The primary change here is that the column calculation algorithm now attempts to render columns as if they were the full remaining height on the page, rather than to render the entire content regardless of how long the page is. The worst-case behavior is effectively the same as that of the previous algorithm (as at least one additional pass would be required to determine how high balanced columns should be, but this applies in both cases), but if content would not fit on the page, this can bail and set the page immediately, rather than continuing significantly more calculations. As an associated benefit, this closes Kozea#1020, as we now handle multiple column breaks (which would force a page break) correctly. A test for this behavior is included.

drboone · 2022-03-17T20:43:59Z

@liZe If you use this version to generate the test document I sent to you, you'll see that it now fails to scale the logo. It also places the address part of the letterhead much lower than it used to. I'm not sure if this is related to this loop fix, or some other commit.

liZe · 2022-03-17T20:59:14Z

If you use this version to generate the test document I sent to you, you'll see that it now fails to scale the logo. It also places the address part of the letterhead much lower than it used to. I'm not sure if this is related to this loop fix, or some other commit.

Could you please send it again? I didn’t keep it.

drboone · 2022-03-17T21:07:40Z

In your email. Thanks for looking!

liZe · 2022-03-19T18:20:12Z

In your email. Thanks for looking!

I get the same rendering with versions 52.5 and current master branch. Which version did you use to get a different rendering?

drboone · 2022-03-19T20:23:32Z

Your merge commit of aschmidtz's changes. The logo is in the top left corner for you, not across most of the page?

liZe · 2022-03-19T23:18:18Z

The logo is in the top left corner for you, not across most of the page?

It’s across the whole page, but it was too with versions 52.5 and 54.2.

drboone · 2022-03-19T23:38:30Z

046f27b is the version I have been running. It appears my reproducer is not valid for anything but the infinite loop.

liZe · 2022-03-20T08:47:16Z

OK, the problem comes from the fact that your document requires presentational hints (the height and width attributes on img). Using the -p option gives the right rendering.

drboone · 2022-03-20T15:04:50Z

Ah, yes, I'd forgotten that for these letters we use the -p option.

drboone · 2022-03-20T15:22:39Z

@liZe @aschmitz Thanks for this fix!

liZe added the crash Problems preventing documents from being rendered label Feb 11, 2020

LukasKlement mentioned this issue Nov 1, 2020

Remove columns support and update docs #1245

Closed

LukasKlement mentioned this issue Jan 28, 2022

WeasyPrint Infinite Loop? #1549

Closed

aschmitz mentioned this issue Mar 17, 2022

perf: improve column handling speed, fix infinite loops #1597

Merged

liZe closed this as completed in #1597 Mar 17, 2022

liZe added this to the 55.0 milestone Mar 17, 2022

grewn0uille mentioned this issue May 12, 2022

The future of WeasyPrint #1232

Open

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Infinite loop in multi-column layout after first (page-)break-before #1020

Infinite loop in multi-column layout after first (page-)break-before #1020

LukasKlement commented Jan 4, 2020

grewn0uille commented Jan 6, 2020

LukasKlement commented Aug 12, 2021 •

edited

Loading

drboone commented Feb 11, 2022 •

edited

Loading

drboone commented Feb 18, 2022

drboone commented Mar 3, 2022

aschmitz commented Mar 3, 2022 •

edited

Loading

drboone commented Mar 3, 2022

LukasKlement commented Mar 3, 2022

drboone commented Mar 3, 2022

aschmitz commented Mar 4, 2022 •

edited

Loading

aschmitz commented Mar 4, 2022

drboone commented Mar 17, 2022

liZe commented Mar 17, 2022

drboone commented Mar 17, 2022

liZe commented Mar 19, 2022

drboone commented Mar 19, 2022

liZe commented Mar 19, 2022

drboone commented Mar 19, 2022

liZe commented Mar 20, 2022

drboone commented Mar 20, 2022

drboone commented Mar 20, 2022

Infinite loop in multi-column layout after first (page-)break-before #1020

Infinite loop in multi-column layout after first (page-)break-before #1020

Comments

LukasKlement commented Jan 4, 2020

grewn0uille commented Jan 6, 2020

LukasKlement commented Aug 12, 2021 • edited Loading

drboone commented Feb 11, 2022 • edited Loading

drboone commented Feb 18, 2022

drboone commented Mar 3, 2022

aschmitz commented Mar 3, 2022 • edited Loading

drboone commented Mar 3, 2022

LukasKlement commented Mar 3, 2022

drboone commented Mar 3, 2022

aschmitz commented Mar 4, 2022 • edited Loading

aschmitz commented Mar 4, 2022

drboone commented Mar 17, 2022

liZe commented Mar 17, 2022

drboone commented Mar 17, 2022

liZe commented Mar 19, 2022

drboone commented Mar 19, 2022

liZe commented Mar 19, 2022

drboone commented Mar 19, 2022

liZe commented Mar 20, 2022

drboone commented Mar 20, 2022

drboone commented Mar 20, 2022

LukasKlement commented Aug 12, 2021 •

edited

Loading

drboone commented Feb 11, 2022 •

edited

Loading

aschmitz commented Mar 3, 2022 •

edited

Loading

aschmitz commented Mar 4, 2022 •

edited

Loading