Differences between revisions 4 and 5
Revision 4 as of 2006-09-15 07:18:02
Size: 21765
Comment: Move the pictures to a more permanent location
Revision 5 as of 2009-09-20 23:52:13
Size: 21829
Editor: localhost
Comment: converted to 1.6 markup
Deletions are marked like this. Additions are marked like this.
Line 4: Line 4:
[[TableOfContents]] <<TableOfContents>>
Line 65: Line 65:
http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_right-wrong.png {{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_right-wrong.png}}
Line 76: Line 76:
http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_right-wrong.png {{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_right-wrong.png}}
Line 97: Line 97:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-2.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-2.png}}||
Line 101: Line 101:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-2.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-3.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-2.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-3.png}}||
Line 159: Line 159:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-2.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-2.png}}||
Line 163: Line 163:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-2.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-2.png}}||
Line 221: Line 221:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-2.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-2.png}}||
Line 225: Line 225:
||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-1.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-2.png||http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-3.png|| ||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-1.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-2.png}}||{{http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-3.png}}||

Contents

1. Characteristics of the fo:float element

This section contains a summary of the part of the spec dealing with floats.

Nb of generated areas

Area class

Notes

0 or 1

xsl-anchor

inline area of dimension 0 if possible, block area otherwise

only if the value of the "float" property is not "none"

1 or more of

xsl-before-float

must be a descendant of a flow object assigned to a region-body

may not be a descendant of an absolutely-positioned block-container

must appear on the same or a following page

may be broken on several pages only if it can't fit on a page alone (without any other float, footnote, or normal content)

xsl-side-float

generates reference areas

xsl-normal

  • Validity checks: an fo:float may not have an fo:float, fo:footnote or fo:marker as a descendant. There are several objects which have such constraints (fo:title, fo:footnote...) but AFAICT the checks for those constraints are not implemented. I'll leave it as is for now, as it is not critical. A general solution will have to be found when implementing such checks.

2. Factorizing out the Handling of Footnotes and Floats

I see only two differences between before-floats and footnotes:

  • footnotes must appear on the same page as their citation, unless there really is no possible pagination which achieve that. Figures may appear on later pages.
  • footnotes may be split so that a part be placed on the following page. Figures may not be split.

Those two differences excepted, the handling is the same. So layoutmgr.PageBreakingAlgorithm could be adapted to no longer handle a list of footnotes, but two (or more) lists of floats; the float machinery could be extracted from PageBreakingAlgorithm and put in a special parameterized class. In fact the two parameters could just be penalties for deferring and splitting:

  • Kind of float

    Defer penalty

    Split penalty

    footnote

    almost infinite

    very much

    before-float

    much

    infinite

(Actually a before-float may be split, but only in the degenerated case where it does not fit alone on a whole page.)

Other possibility: only one parameter defer penalty, and an overriden getFloatSplit method, which would contain the code of the current getFootnoteSplit method for footnotes, and just return 0 for before-floats.

2.1. Changes on the LayoutManager Architecture

When the "float" property is "none", the float must be handled as a normal block; no anchor area is generated. To handle this case I've chosen to directly create a FloatBodyLayoutManager which will render the float in the flow of elements. Otherwise I mimic the behaviour of footnotes: a FloatLayoutManager is created which will insert an anchor in the list of Knuth elements; the corresponding float blocks will be handled by FloatBodyLayoutManager. This is done in LayoutManagerMapping.FloatLayoutManagerMaker, where the value of the "float" property for the corresponding Float node is consulted before creating the LayoutManager.

There are probably things to factorize out between the two LayoutManagers; the addAreas method is for example the same. It may make sense to create an abstract OutOfLineLayoutManager super-class. However, the addAreas method seems to never be called, so it may perhaps be removed and it would become useless to have a common super-class. That's a thing I must find out, this is on my TODO-list.

2.2. A Special Class for out-of-line Objects

First, there are many classes in the layoutmgr package which are related to the Knuth breaking algorithm. As the layoutmgr package already contains a lot of classes, it may make sense to create a new subpackage for the breaking algorithm. That's what I did in the patch, and if this is agreed I'll move the other classes in this subpackage in my next patch.

The OutOfLineRecord class is meant to contain all the logic related to the handling of out-of-line objects:

  • storing progress informations during the breaking process: how many out-of-lines have already been encountered, how many have already been placed, was the last placed object split, etc. The corresponding variables have exactly the same role as the totalWidth, totalStretch, totalShrink variables.
  • methods to manipulate out-of-line objects: register newly encountered ones, find a place where to split, etc.

The progress informations are stored in an internal class of OutOfLineRecord; it is used for two things:

  • to record the current situation during the breaking, when a legal breakpoint is being considered;
  • when an active node is created, to record infos about the out-of-line objects inserted up to the corresponding (feasible) breakpoint.

Why an internal class?

  • as the progress informations are also used by active nodes, this is better to group them in one class rather than having several independant fields. Hence a class.
  • they are one part of the informations stored in an OutOfLineRecord instance. The other informations are the list of Knuth sequences corresponding to out-of-line objects, the list of cumulated lengths, the size of the separator, and so on. Hence an internal class, part 1.

  • they are accessed very often by methods of OutOfLineRecord. This is a convenient way to have access to the fields, while keeping them private for other external classes. Hence an internal class, part 2.

  • as already said, they are also used by active nodes, and not only by an OutOfLineRecord instance. Hence a static class.

2.3. Other Changes

They mostly consist of copy-pasting code relating to footnotes wherever they are referred to, and adapt it to floats. Examples: adding anchors for before-floats in KnuthBlockBox, adding a FloatLayoutManagerMaker in LayoutManagerMapping, handling the addition of a before-float area when necessary, etc.

3. Algorithm for Placing Before-Floats

In Fop, out-of-line objects are handled by an extension of the Knuth breaking algorithm. The handling of before-floats is a bit simpler because they can't be split on several pages like footnotes (excepted in the degenerated case where a float does not fit on one page alone).

Ideally, a footnote should be entirely placed on the same page as its citation. When this is not possible, it may be split, but as few times as possible. See the following figure to understand the issue (the line with the small red sign contains the footnote citation):

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_right-wrong.png

In the first case, the footnote is split on two pages and that's the best we can do. In the second case, there are pieces of the footnote up to 3 pages later; this would disturb the reader who would have too many pages to turn to read the footnote.

To avoid that, the algorithm prevents a footnote to be split if there is a legal breakpoint between the currently considered active node and the currently considered breakpoint, unless this is a new footnote (i.e., not already split). For example, on the preceding figure, every line corresponds to a legal breakpoint. When the line containing the footnote citation is considered for breaking the page, the new footnote may be split. When the following line is considered, there are already many legal breakpoints between the breakpoint of the previous page and that one, so the footnote is not allowed to be split. So the algorithm tries to put the entire footnote on the page, which does not work as it is too big. Thus the breakpoint is discarded (this is not a feasible breakpoint), and same for the following lines. For the first page, the best breakpoint then corresponds to the line with the footnote citation, this allows to put as much of the footnote as possible on this page.

On the second page, no break will be permitted if it splits the footnote, for the same reason as before. Thus the best breakpoint will be the one which puts as many normal lines as possible on the page, plus the entire remaining piece of footnote.

As before-floats may not be split, their handling is simpler than for footnotes. Actually we may use the same algorithm, but this will force the float to be on the same page as its citation, which may give underfull pages as on the following figure:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_right-wrong.png

It would be better to put the citation on the first page together with some other lines and defer the float on the second page.

In fact, just playing with increased demerits for breakpoints with deferred floats is sufficient to have a reasonable amount of floats on the same page as their citations, while preventing underfull pages from being created.

4. Improving the Algorithm

4.1. Rationale

“In the Pagination World, if the worst can happen, it will happen.” — vh

The existing algorithm for footnotes provided a strong and helpful basis for the implementation of before-floats. However, before-floats have specificities of which me may take further advantage; among others:

  • they are likely to have more shrinkability/stretchability than footnotes;
  • it isn't critical to defer them one page.
  • it's best to have a full page with a deferred float rather than an underfull page with no deferred float

The three following examples show one small limitation regarding the footnote handling, along with limitations regarding before-floats. The proposed algorithm below should be able to deal with those limitations.

Footnote

As explained above, a line is not considered to be a feasible breakpoint if there is a previously encountered footnote which must be split. This allows to put as much of the footnote as possible on the current page. Excepted in the following case:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ok-2.png

Here the block in the footnote containing the text "Unbreakable block" actually is breakable. If we now add the property keep-together="always", the result becomes:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-2.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/footnote_no-break-between_ko-3.png

What's happening is the following: if the line containing the footnote citation is placed on the first page, there is no way to put the footnote in an acceptable manner: putting just the first three lines before the unbreakable text leads to an underfull page; putting the whole unbreakable block leads to an overfull page. The former possibility could be a solution: a too-short node would be created to represent this page break. But the actually chosen too-short node is preferred because it contains no footnote split, so its demerits are lower.

The solution would be to split the footnote before the unbreakable block, and to put on the first page one or two more lines of normal text after the line containing the footnote citation. But as already said, the algorithm doesn't allow this possibility.

Before-float 1

Let's consider the following fo document:

<fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format">
  <fo:layout-master-set>
    <fo:simple-page-master master-name="default"
      page-width="12cm" page-height="5.3cm">
      <fo:region-body/>
    </fo:simple-page-master>
  </fo:layout-master-set>
  <fo:page-sequence master-reference="default">
    <fo:flow flow-name="xsl-region-body"
             space-after.minimum="2pt"
             space-after.optimum="6pt"
             space-after.maximum="14pt"
             widows="1" orphans="1">
      <fo:block space-after="inherit">
        This is a block with a float. This is a block with a float.
        The float anchor is just behind this <fo:inline color="blue">word</fo:inline><fo:float float="before" color="blue">
          <fo:block>
            This is the float content. This is the float content.
            This is the float content. This is the float content.
            This is the float content. This is the float content.
            This is the float content.
          </fo:block>
        </fo:float>.
        This is a block with a float. This is a block with a float.
        This is a block with a float. This is a block with a float.
      </fo:block>
      <fo:block space-after="inherit">
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
      </fo:block>
      <fo:block space-after="inherit">
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
      </fo:block>
      <fo:block space-after="inherit">
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
      </fo:block>
    </fo:flow>
  </fo:page-sequence>
</fo:root>

The rendering is the following:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ok-2.png

Now if we set the space-after.optimum value to "8pt", the result becomes:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_main-should-shrink_ko-2.png

What's going on? When a before-float is being considered, the length of the main text already placed on the page is its optimum length, not its minimal length. If there is not enough room for the float, the algorithm doesn't even try to shrink the normal content. Thus the float is deferred to the following page, which might really disturb the user who sees that, obviously, there would be room to put the float on the first page.

Before-float 2

The problem is the same if the float is allowed to shrink but not the content:

<fo:root xmlns:fo="http://www.w3.org/1999/XSL/Format">
  <fo:layout-master-set>
    <fo:simple-page-master master-name="default"
      page-width="12cm" page-height="5.25cm">
      <fo:region-body/>
    </fo:simple-page-master>
  </fo:layout-master-set>
  <fo:page-sequence master-reference="default">
    <fo:flow flow-name="xsl-region-body" widows="1" orphans="1">
      <fo:block>
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
      </fo:block>
      <fo:block>
        This is a block with a float. This is a block with a float.
        The float anchor is just behind this <fo:inline color="blue">word</fo:inline><fo:float float="before" color="blue">
          <fo:block space-after.minimum="3pt"
                    space-after.optimum="4pt"
                    space-after.maximum="9">
            This is the float content. This is the float content.
            This is the float content. This is the float content.
          </fo:block>
          <fo:block>
            This is the float content. This is the float content.
            This is the float content. This is the float content.
          </fo:block>
        </fo:float>.
        This is a block with a float. This is a block with a float.
        This is a block with a float.
      </fo:block>
      <fo:block>
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
        This is a block without a float. This is a block without a float.
      </fo:block>
    </fo:flow>
  </fo:page-sequence>
</fo:root>

The result is the following:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ok-2.png

If we set space-after.optimum to "6pt", this becomes:

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-1.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-2.png

http://people.apache.org/~jeremias/fop/vincent/BeforeFloats/before-float_float-should-shrink_ko-3.png

Here there is an additional interesting issue, which was in part already shown in the footnote case: the first page break corresponds to a too-short node; but this node is still preferred to a node containing additional lines, as among them there would be the line containing the reference to the deferred float, which results to higher demerits for the node. Even if the aesthetic result actually is better.

4.2. Proposed Algorithm

This algorithm is mainly derived from the algorithm presented in the paper "Pagination Reconsidered".

4.2.1. Allowing Underfull Pages

At the paragraph level, underfull lines in justified text are unacceptable, as they create a ragged margin which catches the eye. That's why too-short nodes are handled separately from the other normal nodes and used only as a fallback.

But at the page-sequence level, where the "display-align" property has a default value of "before", underfull pages can be even unnoticeable. And pages are more likely to be underfull than lines as they may contain big paragraphs with no possible stretching.

That's why underfull pages should be acceptable to a certain degree, which ideally would be configurable. Let's say 90%. The algorithm would then accept as feasible the breaks which would lead to a more than 90% full page. Thus in the third example above, the first page break would have a few more lines and would correspond to a feasible break, leading to a slighty underfull page. Even if there would be a deferred float, the fact that this would be a feasible break would make it preferable to the last registered too-short node which is currently chosen.

Of course we may take the amount of underfullness into account when computing a page's demerits, so that full pages are given the preference.

4.2.2. Allowing Out-of-line-only Pages

We could imagine that a document has so many figures that it is sometimes necessary to create a page entirely made of figures, to "flush" the figure list. So the algorithm should be able to handle such cases.

In section 6.10.1.3 of the Recommendation, there is the following sentence: "There may be limits on how much space [...] areas [for out-of-line objects] can borrow from the region-reference-area. It is left to the user agent to decide these limits." Ideally there would be a configuration setting telling which ratio of the page should be filled with normal content; if this ratio is null then pages only made of out-of-line objects would be allowed.

How to handle that? Each time a normal active node is registered, we consider the currently deferred out-of-line objects. If it is possible to make a feasible page, we register a new active node for the corresponding feasible break.

This implies to have two imbricated for loops iterating over before-floats and footnotes, and to create an active node each time some combination of out-of-lines is possible. This will eat some additional memory and processing time, but this would be deactivatable (set a non-null minimum ratio of normal content), and this feature would be dedicated to complex book-like documents where pagination quality is more important than processing time.

Actually those loops may also be desirable when considering a "normal" page break. Because, for example, splitting a footnote two times might help solve an otherwise impossible pagination problem in later pages.

4.2.3. Taking Advantage of Out-of-lines shrinking/stretching

The current algorithm does not consider the possibility of shrinking/stretching an out-of-line object to make it fit on the current page. It wouldn't be too difficult to implement this possibility.

4.2.4. Refining the Demerits Computation for Deferred Out-of-line Objects

A given value is added to the demerits of a feasible break if there are dangling references. The idea would be to multiply this value by the page difference between the reference and the out-of-line. Same for split footnotes: we would multiply the corresponding demerits by the number of times the footnote is split.

This should allow to avoid the special treatment for footnotes (the noBreakBetween method) which doesn't work well in the situation above. And generally a pagination which would split a footnote too much would have so high demerits that it should never be preferred.

As a consequence, there may be more considered feasible breaks than currently, but again we are in the case of book-like documents where we can afford the additional memory consumption.

GoogleSummerOfCode2006/FloatsImplementationProgress/ImplementingBeforeFloats (last edited 2009-09-20 23:52:13 by localhost)