1640197 - Investigate implementation of fallback "slicing" fragmentation using display list

Status: RESOLVED FIXED

(Core :: Layout, task, P1)

Description

[Sean Voisen (:svoisen)]

Mats has proposed an approach to a fallback fragmentation strategy using display lists, which may be "good enough" in many cases: https://gist.github.com/MatsPalmgren/8eb65464f08850597877ab155e856a0c

This bug is for tracking work to investigate and potentially implement this idea.

Comment 1

[Daniel Holbert [:dholbert]]

I'm planning on taking a look at this soon. Assigning to myself so that it's on my radar.

Comment 2

[Mats Palmgren (inactive)]

Attachment: page-content-dup-hack

This is just some experiment I did with using BuildDisplayListForExtraPage / SetBuildingExtraPagesForPageNum for creating the clones, and then translating/clipping that into the correct position for the target page.

Comment 3

[Jonathan Kew [:jfkthame]]

Miko, would you be able to have a look at this, particularly from a DisplayList point of view, and perhaps help us move it forward? See Mats' gist (comment 0) for background on what we're hoping to do here. Thanks!

Comment 4

[Miko Mynttinen]

(In reply to Jonathan Kew (:jfkthame) from comment #3)

Miko, would you be able to have a look at this, particularly from a DisplayList point of view, and perhaps help us move it forward? See Mats' gist (comment 0) for background on what we're hoping to do here. Thanks!

I'm taking a look at this.

Comment 5

[Sean Voisen (:svoisen)]

Tracking for 81 because we'd really like to get this fallback implemented in time for that release to coincide with other printing improvements.

Comment 6

[Mats Palmgren (inactive)]

Attachment: Testcase #1

Comment 7

[Mats Palmgren (inactive)]

Attachment: Testcase #2

Comment 8

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 2: Add an additional offset to reference frame r=mattwoodrow

Comment 9

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 2: Relax assertion from being an ancestor to sharing a common ancestor

Depends on D88639

Comment 10

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 3: Include overflowing content from the previous pages in display list for nsPageContentFrame

Depends on D88640

Comment 11

[Mats Palmgren (inactive)]

Attachment: propagate OverflowIncomplete status if we have overflow or previous pages have it

So here's a rough sketch of what I meant with propagating an incomplete status up to PageSequenceFrame to let it know that it should create another page. It creates the necessary pages to render Testcase #2, but it generates one (unnecessary) blank page at the end since I just copied the GetPreviousPageContentFrames loop you wrote (which tests if previous pages overflows onto this page, whereas in this case we should test if that overflow overflows THIS page too).

Also, I wonder if all this can be simplified by storing the overflow on the frames themselves (nsPageContentFrame or nsPageFrame) and accumulating it so that say if page 1 overflows 1000px and a page size is 700px then page 1 would store 1000px, and page 2 would store max(300px, <it's own overflow>) etc. Then we don't need GetPreviousPageContentFrames (which is O(n^2)) at all since we only need to peek at the previous continuation to get the accumulated remaining overflow. Note that these frame classes are only used for printing so we don't need to worry about memory size - we can add more fields if that helps.

Comment 12

[Miko Mynttinen]

edit: This was confusion about layout debugger.

Comment 13

[Miko Mynttinen]

Attachment: Bug 1640197 - Part x: Create more pages if needed [WIP]

Depends on D88641

Comment 14

[Miko Mynttinen]

Attachment: Bug 1640197 - Part x: Use transforms instead of reference frame offsets

Depends on D89926

Comment 15

[Daniel Holbert [:dholbert]]

Once it's reviewed, I think this could go ahead and land without the "offsetting to create space for expected overflow" pieces, BTW, as long as it's pref-controlled and preffed off for release. Probably safest to have it preffed on for nightly-only, perhaps? And that means: there's no reason to try to get any of it in before the soft freeze this week; but it'd be nice to have it next week or soon after, to get some Nightly testing in the 83 cycle.

(We can land the offsetting pieces in separate bugs/patches, I think, and then enable the pref beyond Nightly once we're confident that we're not making any/many scenarios worse. [Presumably we'll be making lots of scenarios better, of course.])

Comment 16

[Daniel Holbert [:dholbert]]

Also, FYI: bug 1631452 will add an additional offset & transform to nsPageFrame painting, to support "pages-per-sheet", so that we can e.g. end up with a sheet of paper (PrintedSheetFrame) that has a grid of 4 shrunken pages (nsPageFrames) on it. We should test this feature & that feature together and be sure they play nicely together, since I can imagine that the page-offset-computation here might get confused by pages being laid out side-by-side on the same sheet, for example. Or it might just work!

(I'm interested in testing out some scenarios locally, but phabricator seems to say that https://phabricator.services.mozilla.com/D89927 has build errors right now, so I'm not sure I can test -- but let me know if/when this is at a state where I could apply the patches & build with it locally & try it out!)

Comment 17

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 1: Relax assertion from being an ancestor to sharing a common ancestor r=mats

Comment 18

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 3: Include overflowing content from the previous pages in nsPageFrame display list r=mats

Depends on D90424

Comment 19

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 4: Create more pages for vertical overflow r=mats

Depends on D90425

Comment 20

[Miko Mynttinen]

Thank you for helping out with this Daniel.

(In reply to Daniel Holbert [:dholbert] from comment #16)

Also, FYI: bug 1631452 will add an additional offset & transform to nsPageFrame painting, to support "pages-per-sheet", so that we can e.g. end up with a sheet of paper (PrintedSheetFrame) that has a grid of 4 shrunken pages (nsPageFrames) on it. We should test this feature & that feature together and be sure they play nicely together, since I can imagine that the page-offset-computation here might get confused by pages being laid out side-by-side on the same sheet, for example. Or it might just work!

I agree, these offset computations are tricky and probably very easy to break. The current algorithm takes the overflow area that does not fit on the page, builds a display list for it, wraps it in nsDisplayTransform, and moves it to the beginning of the next page with an appropriate clip and offset.
At the moment the offset calculations work under the assumption that "excess overflow" of a page has been accumulated on pages following (determined by calculating the trailing page area down to the current page from the page that had overflow). This is probably not the most correct or optimal way of doing this, I think the right approach depends on how bug 1665214 (or bug 1631452) will change the frame tree shape.

(I'm interested in testing out some scenarios locally, but phabricator seems to say that https://phabricator.services.mozilla.com/D89927 has build errors right now, so I'm not sure I can test -- but let me know if/when this is at a state where I could apply the patches & build with it locally & try it out!)

Sorry about that, it was a bit messy because I had patches for two different approaches, because it was not obvious which one was better. The patches up now should work. The last patch of the stack is my attempt at tweaking reflow to create extra pages, which works in most cases but occasionally creates too many.

Comment 21

[Daniel Holbert [:dholbert]]

Thanks! I tried out my pages-per-sheet patch stack with this, and it seems to interact just fine -- we end up producing the same layout, regardless of whether I'm doing 1 page per sheet vs 4 pages per sheet. (I used attachment 9171100 [details] as my testcase.)

So, that's good news!

Comment 22

[Daniel Holbert [:dholbert]]

Attachment: testcase #3

Comment 23

[Daniel Holbert [:dholbert]]

Attachment: testcase #4 (same as 3 but with a vertical writing-mode)

Comment 24

[Daniel Holbert [:dholbert]]

Attachment: screenshot of testcase 3 (note a few missing numbers)

Here's a screenshot of testcase 3 in print-preview, with the patch stack as it stands right now.

It looks like some of the content is getting lost at the page-boundary here. We're missing ~2.5 lines of content (we paint half of "49" and then jump to "52"), so there's some bookkeeping that's getting mixed up in terms of offset computation for the preserved overflow, I think.

Comment 25

[Daniel Holbert [:dholbert]]

Attachment: testcase #5 (like 4, but now with a really long string of text that overflows in inline axis)

Comment 26

[Daniel Holbert [:dholbert]]

Testcase #4 and #5 are meant to illustrate the vertical-writing-mode problem that I brought up in phabricator. Ideally, we should really fix them here before landing... But I'm not entirely opposed to addressing them in a followup.

Essentially: for a document with writing-mode: vertical-lr (or vertical-rl), its block axis (the axis we fragment/paginate in) is the horizontal axis. So content that runs off the side of page 1 is what should end up on page 2, and content that runs off the bottom of page 1 should get lost. (This is the opposite of what happens in a document with a horizontal writing-mode.)

This axis-swapping works just fine with our regular fragmentation pipeline, but we get it backwards with this patch stack, due to its dependency on strictly vertical coordinates (y values and heights).

This should be fairly straightforward to address - it just requires that we look up overflow in terms of logical coordinates and APIs (LogicalRect, LogicalSize, etc; and the APIs that return those structs on nsIFrame) and the "B" (block-axis) components of those structs.

STR to see issues with testcase #4 and #5:

1. Print the testcase, in a build with this bug's patch stack applied.
2. In "More Settings", change "Scale" to "100% (not fit-page-width), to simplify things a bit.
3. Look at the rendered preview.

EXPECTED RESULTS:

• In both testcases, the numbered list should be continued across all of the pages (just as it does for testcase 3, in a build with the patches here, aside from the bookkeeping noted in comment 24).
• In testcase #5, the "aaaaa..." should be truncated and should not show up on any other pages (just as it would if we added this to testcase 3)

ACTUAL RESULTS:

• In both testcases, the numbered list doesn't show up beyond the first page.
• In testcase #5, the "aaaa...." is painted on subsequent pages, even though it ran off the bottom (inline-axis-end edge) of the first page, and the subsequent pages are supposed to contain content that ran off the right side (the block-axis-end edge) of the first page. In other words, page 2,3,etc. end up containing content that ran off of two different sides of page 1 (overflow from its bottom and right edge), which creates a weird frankenstein mashup of overflow. :)

Comment 27

[Daniel Holbert [:dholbert]]

Attachment: screenshot of how testcase 5 is misrendered by patch stack as of 10/5

ACTUAL RESULTS:
[...]

• In testcase #5, the "aaaa...." is painted on subsequent pages.

Here's a screenshot to demonstrate what this looks like & how it's weird. (page 2 ends up getting content that ran off the right side of page 1, via our regular fragmentation codepath; and it gets content that ran off the bottom of page 1, via this new overflow-preserving codepath. Really, it should only get content that ran off the right side, since that's the block-axis "end" edge of the page.)

Comment 28

[Mats Palmgren (inactive)]

I agree we can fix vertical-writing-mode issues in follow-up bug. It's probably better if someone familiar with logical axes work on that.

It looks like some of the content is getting lost at the page-boundary here

This seems like something we should fix here though. I guess we don't account for the page margin(s) somehow?

Comment 29

[Daniel Holbert [:dholbert]]

OK - I filed bug 1669333 on the vertical writing-mode issues.

Comment 30

[Daniel Holbert [:dholbert]]

BTW: I'll be on parental leave after this Friday. If this ends up going up for re-review after that point, I think it'd be fine for mats to review the changes.

In other words, this is essentially "r=me with changes to address the nits/issues that I brought up (including testcase 3 / comment 24); and those changes themselves deserve a review; and I think it'd be fine for mats to be the one to review those changes, if they're up after I'm on leave.

Comment 31

[Mats Palmgren (inactive)]

Attachment: Testcase #6

Comment 32

[Mats Palmgren (inactive)]

Attachment: Screenshot of Testcase #6

It appears we still don't account for the gap between the pages correctly. Compare Testcase #6b.

Comment 33

[Mats Palmgren (inactive)]

Attachment: Testcase #6b

Here's the same test as #6 but with a block instead of inline-block.

Comment 34

[Mats Palmgren (inactive)]

Attachment: Screenshot of Testcase #6b

This is how far I would expect the inline-block in Testcase #6 to reach.

Comment 35

[Mats Palmgren (inactive)]

Attachment: Testcase #7 (overlapping text and borders)

Comment 36

[Mats Palmgren (inactive)]

Attachment: fix the paint order

Here's a patch that I think should fix the painting order dholbert pointed out.
I think the problem with the canvas background hiding everything is this line:
https://searchfox.org/mozilla-central/rev/c2e3ac11be4837718c2604e58085fbc8252b69dd/layout/generic/nsPageFrame.cpp#614
so we need to make sure content contains all the content, also from previous pages, so that this item is below all content.

Comment 37

[Mats Palmgren (inactive)]

Attachment: Screenshot of Testcase #7 with "fix the paint order" patch

So the green text is now correctly painting on top of the black text, but this reveals another bug: note that the green border paints over both the blue and black borders. This is wrong, it should only paint over the blue (dashed) border, not the black border (as it does in non-print mode). The root of that problem (I think) is that we're using BuildDisplayListForStackingContext for painting the previous pages, which puts everything into the Content display list. We really need to use the correct display lists when painting the overflow from previous pages to get the rendering the CSS specs require.

Comment 38

[Mats Palmgren (inactive)]

Attachment: WIP hack to fix display lists

Hmm, I thought something like this would fix the border painting order but it doesn't...

Comment 39

[Mats Palmgren (inactive)]

Oh, now I see, it seems the black border doesn't extend far enough because of some clipping issue?
(Try Testcase #7 but without the green border.)

Comment 40

[Mats Palmgren (inactive)]

Attachment: Testcase #8

Comment 41

[Mats Palmgren (inactive)]

Given our new testing policy, I think this bug needs to have some regression tests before it can land. See the reftests in layout/reftests/pagination/ for examples. See layout/tools/reftest/README.txt for documentation. (Basically, just add class="reftest-paged" to the <html> element and then write a normal reftest. I think we snapshot 800x1000 pixels as usual which means about 3 pages are included.)

Comment 42

[Miko Mynttinen]

Attachment: Bug 1640197 - Part 5: Add reftests r?mats

Depends on D90426

Comment 43

[Mats Palmgren (inactive)]

Attachment: this is the fix I'd suggest for part 4

Comment 44

[Mats Palmgren (inactive)]

Attachment: prevent overflowing fixed pos from triggering new pages

This should fix the layout/reftests/bugs/582037-2a.html hang that was caused by creating an infinite number of pages due to overflowing fixed pos frames (which were then replicated on the new page).

Comment 45

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/a15fd343016b
Part 1: Relax assertion from being an ancestor to sharing a common ancestor r=mats
https://hg.mozilla.org/integration/autoland/rev/97be67a34ea7
Part 2: Add an additional offset to reference frame r=mattwoodrow
https://hg.mozilla.org/integration/autoland/rev/3ce80153e304
Part 3: Include overflowing content from the previous pages in nsPageFrame display list r=dholbert,mats
https://hg.mozilla.org/integration/autoland/rev/52b812a1c2f7
Part 4: Create more pages for vertical overflow r=dholbert,mats
https://hg.mozilla.org/integration/autoland/rev/ac0b9d84052b
Part 5: Add reftests r=mats

Comment 46

[Cosmin Sabou [:CosminS]]

https://hg.mozilla.org/mozilla-central/rev/a15fd343016b
https://hg.mozilla.org/mozilla-central/rev/97be67a34ea7
https://hg.mozilla.org/mozilla-central/rev/3ce80153e304
https://hg.mozilla.org/mozilla-central/rev/52b812a1c2f7
https://hg.mozilla.org/mozilla-central/rev/ac0b9d84052b