xmlgraphics-fop-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From Apache Wiki <wikidi...@apache.org>
Subject [Xmlgraphics-fop Wiki] Trivial Update of "GoogleSummerOfCode2006/FloatsImplementationProgress" by VincentHennebert
Date Fri, 04 Aug 2006 10:38:17 GMT
Dear Wiki user,

You have subscribed to a wiki page or wiki category on "Xmlgraphics-fop Wiki" for change notification.

The following page has been changed by VincentHennebert:
http://wiki.apache.org/xmlgraphics-fop/GoogleSummerOfCode2006/FloatsImplementationProgress

The comment on the change is:
This page is becoming too big: split into several sub-pages

------------------------------------------------------------------------------
- #pragma section-numbers on
- 
  This page will contain various informations about how the project progresses: thoughts,
issues, design decisions, etc.
  
- '''Contents'''
- [[TableOfContents()]]
+ = Contents =
+ This page is split into the following sub-pages:
  
- '''News'''
+ /Phase1Documentation: various documentations about the Knuth approach and pagination techniques
+ 
+ /ImplementingBeforeFloats: summary of the spec, study of the footnote handling, presentation
of the placement algorithm for before-floats
+ 
+ /ImplementingSideFloats: formalization of the spec
+ 
+ = News =
  
  August 02
   Study of side-floats: understand, summarize, formalize the specs (XSL-FO and CSS2); clear
uncertainties.
@@ -26, +30 @@

  
  
  June 19
- 
   Deep study of the breaking algorithm, in order to propose a refactoring which will prepare
the implementation of floats: factorize out things common to line- and page-breaking, generalize
the handling of footnotes to turn it into the handling of out-of-flow elements. A pseudo-language
version should be published soon.
  
  
  June 12
- 
   Further reading of the source code. I'm beginning to have a good understanding of the breaking
algorithm.
  
  
  June 07
- 
   I've remained silent those days, because of deep diving into Fop's source code... Pending
tasks:
    * integrate the comments from Simon and Jeremias on my latest changes to this page;
    * write a review of Plass' thesis.
  
- = Phase 1: Documentation =
- I'm planning to read the following literature:
-  * "Digital Typography", Knuth: glue/box/penalty model, optimal line-breaking algorithm
-  * "Pagination Reconsidered", Brüggemann-Klein, Klein, Wohlfeil: a better algorithm for
placing floating objects than TeX's one.
-  * Pages of this Wiki related to the Knuth Approach
-  * Have a look at Simon Pepping's generalized glue/box/penalty model.
- 
- == "Digital Typography": Breaking Paragraphs into Lines ==
- The algorithm works when each line of the paragraph has a different length. This may be
interesting for implementing side-floats, provided that we know in advance which height each
line will have. And I think this may depend on the line-stacking strategy.
- 
- There are three main aspects which characterize the Knuth approach:
-  * build a sequence of glue/box/penalty elements from some input data;
-  * define a somewhat arbitrary formula used to compute the demerits of each break, and which
is to be minimized;
-  * the algorithm itself, which corresponds to the finding of a shortest path in an acyclic
graph. The nodes are breakpoints and each edge is tagged by the demerits of the corresponding
line.
- 
- To enter a bit in the details:
-  * a line may be broken either at a penalty item, or at a glue immediately following a box;
-  * when a line is broken, all of the glue/penalty items at the beginning of the line up
to the first box are removed.
-  * those properties may be utilized to achieve various effects, such as ragged-right/ragged-left/centered
lines. Many effects rely on the fact that a negative value may be given to the stretching
of a glue
-  * the definition of the to-be-minimized formula may vary according to the criteria of optimization.
In the formula used by TeX to justify text, there are three criteria:
-    * the badness beta, related to the adjustment ratio of the line (how much it is stretched/shrinked);
-    * the penalty pi, if the line breaks at a penalty item;
-    * an additional penalty alpha, if this line and the previous ones end at a flagged penalty
item.
-  Those three values are mixed together to compute the line's ''demerit''. The algorithm
will find a set of lines with a minimal sum of demerits.
- 
- Regarding (before-)floats:
-  * the fo:float element (with the "float" property set to "before") will have to be converted
to a sequence of glue/box/penalty elements, which themselves will have to be inserted at the
beginning of certain pages;
-  * the formula used to determine the optimality of floats placements should be retrieved
from the "Pagination Reconsidered" paper. I still have to see how to mix it (if any) with
the formula currently used to break pages. I assume that it is different from the formula
used for paragraphs, as there are different constraints (more to come when I've looked at
the code);
-  * the line-breaking algorithm isn't designed to handle a floating sequence of g/b/p items.
That is, a subsequence that is not fixed in the larger general sequence, but may be put at
other places and possibly split.  The algorithm will have to be extended, probably by the
algorithm found in "Pagination Reconsidered";
-  * All what have been stated so far may be invalidated by further readings...
- 
- == "On the Pagination of Complex Documents" ==
- From Brüggeman-Klein, Klein, Wohlfeil. This article may be found [http://wwwpi6.fernuni-hagen.de/Publikationen/tr234.pdf
here].
- Also, from the same authors, the article [http://wwwpi6.fernuni-hagen.de/Publikationen/tr205.pdf
"Pagination Reconsidered"] gives the details of the algorithm.
- 
- === Some Theoretical Background ===
- This article let me understand some abstract background of document layout. In fact, document
layout is somewhat similar to a [http://en.wikipedia.org/wiki/Bin_packing_problem bin packing
problem]: bins correspond to pages, objects to typeset material of some height. Those objects
usually come from different flows: before-floats, main flow, footnotes. The order of each
flow must be respected (a figure appearing after another one in the list must appear later
on the pages), but there is some freedom in choosing from which flow the next typeset element
will be taken.
- 
- An optimal way of putting those elements on the pages must be found. In other words there
is some cost function to minimize. This cost function should reflect what a human would call
a good pagination; among various criteria we may cite the following: figures should appear
as near to their first reference as possible; footnotes ''must'' appear on the same page as
their citation; facing pages (or columns) should be balanced; etc.
- 
- As for packing problems, page layout will usually be a [http://en.wikipedia.org/wiki/Combinatorics
combinatorial] NP-hard problem. However, if the cost function has some particular properties
(namely [http://en.wikipedia.org/wiki/Optimal_substructure optimal substructure]), it becomes
possible to solve it in polynomial time by using [http://en.wikipedia.org/wiki/Dynamic_programming
dynamic programming]. The cost function used by Knuth and Plass for computing demerits of
each line of a paragraph has such a property. 
- 
- For the page layout problem, the main issue is then to find a cost function:
-  * which correctly reflects the quality of a layout;
-  * which has the right properties to make it possible to use dynamic programming for minimizing
it.
- 
- Note that other techniques than dynamic programming may be used to layout pages. For example,
by using some heuristic approach combined to genetic algorithms or simulated annealing (like
in [http://citeseer.ist.psu.edu/johari97automatic.html this article]). But exploring those
approaches would lead us much too far. Let's concentrate on the dynamic programming approach
implemented in Fop.
- 
- === Comments on the Article ===
-  * It is assumed that paragraphs have already been broken into lines. The main restriction
of such an assumption is that it won't be possible to apply this method to sequences of pages
of different widths. However, this shouldn't prevent us from registering several layouts of
the same paragraph with differing numbers of lines. Thus it would be possible to choose a
layout with fewer lines to avoid an orphan, for example.
-  * In his thesis (see below), Plass defines a badness function for measuring pagination
quality that makes the problem NP-hard. In this article, another function is used which in
the authors' opinion better reflects a human's judgment, and for which there is a polynomial
solution. In short, they use the number of page turns necessary to read the document, that
is, the total number of pages + the number of page turns caused by figures appearing on a
different page from their citations. Plass used the sum of the squares of page differences
between figures and their citations.
-  * The page model used to explain the algorithm is pretty similar to the one used by FO:
an optional figure region at the top of the page, with optional glue separating it from the
text. Good point.
-  * The authors utilize the fact that on double-sided documents, a figure may appear on the
left page if its citation is on the right page. I think the XSL-FO spec doesn't allow this,
but perhaps that a user-configurable extension...
-  * The computation time of the pagination algorithm presented in this paper is proportional
to the number of text lines times the number of figures. Note that this article does not deal
with footnotes, but it should be easy to extend it to handle them.
-  * It is possible to tweak the algorithm to allow pages which are not entirely full (yet
still with balanced facing pages). Indeed sometimes it is impossible to find a layout which
respects all of the contraints (full pages, no widow/orphan, keeps...)
-  * Although the algorithm assumes that each line of text is separated by some glue, it only
relies on their minimum and maximum values. It doesn't take the optimal value into account.
And as it tries to minimize the total number of pages, we may end up with spaces systematically
set to their minimum value. Indeed, if there are no before-floats nor footnotes, it will obviously
be the case. I think this may break the XSL-FO spec; at least we can expect complaints from
users.
-  * Related to this: the possibility to break a page is binary: allowed or not. This constraint
is IMO too heavy: although an orphan is undesirable, it should be acceptable when no better
layout is possible. In fact this algorithm doesn't utilize the whole range of penalty values
available in the Knuth model; only two are allowed, 0 and infinity.
- 
- === Resulting Thoughts ===
- The algorithm cannot be used directly as it is presented, mainly because of the two last
items of the previous section. However, it provides a strong basis IMO. Some points:
-  * There may be cases where it is impossible to find a layout which fulfills all of the
criteria. We may consider to perform a second pass with some relaxed properties, but:
-    * can we afford the additional computation time?
-    * which properties to relax, in which order? Possibilities:
-      * orphans/widows properties; but contrary to TeX, in XSL-FO it is only possible to
define the number of orphans/widows, not a penalty associated to them.
-      * keep properties: those may have integer values that allow for some flexibility
-      * page fullness: AFAICT the XSL-FO spec does not impose that pages be full. And as
explained earlier, the algorithm can use this possibility. According to the article this becomes
quite easy to find a layout just by allowing pages to be only 90% filled. This might even
become possible to perform only one pass (which would ideally find the optimal pagination
when possible, and one with some percentage of fullness otherwise). (See also the recent thread
on fop-dev on this subject.)
-  * There is a free bonus implied by this algorithm: this should give pages which are vertically
justified [[FootNote(don't forget to have a look at Luca's LayoutExtensions on this issue)]].
That is, the bottoms of pages should coincide with the bottom of the region-body area. The
only exception would be in "relaxed mode", when a percentage of fullness is introduced. Such
a feature should remain optional, however. But I think the exact same situation occurs with
justified or ragged-right text: the algorithm is the same, just the glues are actually stretched/shrinked
or left as is.
-  * BTW, is there in XSL-FO a way of determining if the document is single- or double-sided?
We can check if separate page masters are used for even and odd pages. Such a check should
be reliable, though. Anyway, such a thing may probably be deferred to a fine-tuning period,
when we have a working basic implementation.
-  * The algorithm may be generalized to allow several kinds of floats e.g., tables and figures.
In such cases, even if the order of each float sequence must be respected, this is possible
to place a table before a figure even if it is referenced later in the main text. That said,
XSL-FO defines only one kind of before-floats. Anyway, there is room for future Fop extensions
IMHO...
- 
- When there are no figures nor footnotes, pagination becomes equivalent to breaking paragraphs
into lines. In such a particular case the Knuth algorithm may be used. It would thus be great
to find a cost function and an associated algorithm that become equivalent to line-breaking
in such a case. Anyway, this would be great to utilize the full potential of the g/b/p model
for page-breaking. And, moreover, to rely as much as possible on the current source code.
More to come when I have looked at it.
- 
- 
- == "Optimal Pagination Techniques for Automatic Typesetting Systems" ==
- Michael Frederick Plass -- PhD thesis
- 
- === Introduction ===
- Plass starts by having a look at the practices which were in use in the past. In short,
compositors were mostly performing a first-fit pagination, because of the difficulty to look
ahead and because re-typesetting the n-1 previous pages to have a better-looking page n demanded
too much time. Footnotes were particularly difficult to handle. Others problems were balanced
facing pages, and obviously floats placement.
- 
- The g/b/p model used for line-breaking does not readily apply to page-breaking, it must
be extended with some "insert" operator to handle figures and footnotes.
- 
- === Pagination may be an NP-complete Problem ===
- The basic algorithm which consists in choosing the best pagination among all of the possible
ones is obviously exponential. But depending on the chosen badness function, the problem may
become solvable in polynomial time.
- 
- Basically Plass shows that, among others, "quadratic" badness functions lead to an NP-complete
problem. Such functions compute the square of the differences between the page numbers of
their citations and the page numbers of their corresponding figures.
- 
- In reality this is a bit more subtle. Indeed, with certain constraints, quadratic functions
may be solvable in polynomial time. Plass actually shows that this is quite easy to choose
constraints which makes the problem exponential. For example, simply allowing glue between
the elements suffices to make the problem NP-complete. The issue is then to find the right
constraints (number of citations per figure, number of objects per page, constant page size
or not, and so on) and the right badness function, so that the problem still is a good representation
of the reality yet is solvable in polynomial time.
- 
- === Making Pagination Polynomial ===
- It may be interesting to quickly explain the case where there are no footnotes nor figures.
The problem becomes equivalent to line-breaking and lets understand the main basis on which
the whole dynamic programming approach relies.
- 
- We define B,,jk,, to be the badness corresponding to the best way to put the first j lines
on the first k pages. Then the following formula holds:
-          B,,jk,, =  min,,0<=i<j,,  {B,,i k-1,, +  β,,ijk,,}
- where β,,ijk,, is the badness due to placing lines i+1 through j on page k. The best way
to put the first j lines on the first k pages only depends on the best ways to put i lines
on the first k-1 pages. The only problem is to find this particular i for which (the badness
of the first k-1 pages) + (the badness of page k) will be minimal.
- 
- We can easily see the recursive nature of this problem. The rest, well, "only" corresponds
to implementation details.
- 
- When introducing footnotes and figures, the challenge is to find a formula which has a similar
structure. Plass begins with a formula which computes the distance (in absolute value) between
a figure and each(!) of its citations. The problem is solvable but the constraints are unrealistic:
their may be only one type of element on each page, either text or a figure. Plass then generalizes
the problem by handling any number of independant flows (normal text, figures, tables, etc.),
but again with only one element per page.
- 
- Ok, I've decided to stop here. At the end of the paragraph, Plass presents a differently
generalized problem and tries to find sufficient conditions which make it solvable by dynamic
programming. In this case the previous weird constraints are relaxed: their may be any number
of element on each page, several flows, several references from any flow to any other, etc.
Then he formulates the cost function as depending on 4 independent arbitrary sub-functions,
which give some freedom to the characterization of good pagination.
- 
- Then there is an entire chapter describing an implementing algorithm, which is very similar
to the line-breaking algorithm. Here I think it is more interesting to refer to the work of
Brüggemann et al., which is easier to read and more directly re-usable than Plass' work.
It will only have to be adapted to the g/b/p model, which shouldn't be too difficult.
- 
- It may be worth returning to Plass' work if we encounter unexpected difficulties during
the implementation of floats (e.g., the chosen algorithm doesn't provide satisfying results),
as it provides a strong theoretical basis. For now I think I know enough to proceed to the
implementation.
- 
- 
- == The Fop Source Code ==
- Even if it is well explained, the Knuth line-breaking algorithm isn't that easy to understand.
ATM I've concentrated on the class layoutmgr.!BreakingAlgorithm, which contains the part of
the algorithm which is common to page- and line-breaking. It is splitted in parts which follow
pretty closely those described in "Digital Typography". It relies on the following skeleton:{{{
- findBreakingPoints(a paragraph, max allowable ratio for stretching, force or not the finding
of breakpoints)
-     initialize the various fields and variables
-     For each Knuth element of the paragraph Do
-         update totalWidth, totalStretch, totalShrink
-         If the element is a feasible breakpoint Then
-             > considerLegalBreak(at this element)
-         EndIf
-     EndFor
-     If no set of feasible breakpoints could be found Then
-         reactivate the last node and restart the algorithm from it
-     EndIf
-     Select some active nodes among the available ones
-             > filterActiveNodes()
-     For each remaining active node Do
-         Compute the corresponding set of optimal breakpoints
-                 > calculateBreakPoints
-     EndFor
- 
- 
- considerLegalBreak(Knuth element)
-     For each currently active node Do
-         compute the adjustment ratio of a line starting at the active node and ending at
this element
-         If the adjustment ratio is unacceptable Then
-             deactivate this node
-         Else
-             compute the fitness class of the corresponding line
-                     > computeFitness
-             update the total demerits by adding the demerits of this line
-                     > computeDemerits
-             If the result is better than the best recorded demerits for the given fitness
class Then
-                 register this new best active node
-                         > BestRecords.addRecord
-             EndIf
-         EndIf
-         (perform something when the adjustment ratio is unacceptable and we are in forced
mode)
-     EndFor
-     add new active nodes for breaks at this element
-             > addBreaks
- 
- 
- addBreaks(element ending the line, line number)
-     compute the new totalWidth, totalStretch, totalShrink (after this element)
-     For each fitness class Do
-         If the recorded best active node for this fitness class is to be retained Then
-             create a new active node for a break from this node to the element
-         EndIf
-     EndFor
- 
- 
- calculateBreakPoints(last active node, corresponding paragraph, corresponding number of
lines)
-     For j = number of lines DownTo 1 Do
-         breakpoint = node.element
-         node = node.previous
-     EndFor
- }}}
- 
- 
- = Implementation of Before-Floats =
- == 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'''||
- ||<|2>0 or 1 ||<|2(>xsl-anchor||inline area of dimension 0 if possible, block
area otherwise||
- ||only if the value of the "float" property is not "none"||
- ||<|6> 1 or more of||<|4>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.
- 
- == 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.
- 
- === 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.
- 
- === 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.
- 
- === 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.
- 
- == 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://atvaark.dyndns.org/~vincent/footnotes.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://atvaark.dyndns.org/~vincent/floats-underfull.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.
- 
- 
- = Implementation of Side-floats =
- == Formalizing the Problem ==
- The specification of side-floats is in part taken from the CSS2 recommendation and adapted
to XSL-FO. It may be useful to summarize and reformulate the spec to have a precise understanding
of how side-floats should be handled.
- 
- An fo:float element with the "float" property set to "start" or "end":
-  * generates a ''block-area'' of class "xsl-side-float", which also is a ''reference-area''
-  * is placed as a child of the nearest ancestor reference-area of the anchor-area or as
a child of a later reference-area of the same chain
-  * the length in the inline-progression-direction is the intrisic length of the area
-  * border and padding should be set to zero on all edges of the side-float; the space properties
don't apply to fo:float; as a consequence, the allocation-rectangle, border-rectangle, padding-rectangle
and content-rectangle of a side-float area are the same
-  * block-areas before and after the side-float flow in the block-progression-direction as
if the float didn't exist. Line-areas are reduced to make room for the float
- 
- To formalize the rules of placement of side-floats, we will set up the following coordinate
system:
-  * the x-axis goes into the inline-progression-direction of the nearest ancestor reference-area;
-  * the y-axis goes into the block-progression-direction;
-  * the origin is the point of the reference-area's content-rectangle which is at the intersection
of the start-edge and before-edge.
- 
- In such a coordinate-system, a side-float area is characterized by the (x,y) coordinates
of its "start-before point", that is, the point of its allocation-rectangle (or border-rectangle,
or padding-rectangle, or content-rectangle) which is at the intersection of the start-edge
and before-edge.
- 
- http://atvaark.dyndns.org/~vincent/side-floats_coordinate-system.png
- 
- === Rules for Placing Side-floats ===
- Some definitions:
-  * we will call a start-float the block-area generated by an fo:float with "float"="start"
or "left". Same for end-float
-  * we will note start-float ≺ start-float' if start-float precedes start-float'; that
is, the generating fo:float for start-float is before the generating fo:float for start-float'
in the fo tree.
- 
- The nine rules given in the description of the "float" property may then be reformulated
like the following:
-  1. for a start-float, x ≥ 0
-  for an end-float, x + ipd ≤ ipd,,ref-area,,
-  2.#2 ∀ start-float' ≺ start-float, x > x' + ipd' or y > y' + bpd'
-  ∀ end-float' ≺ end-float, x + ipd < x' or y > y' + bpd'
-  3.#3 ∀ start-float s, ∀ end-float e, [y,,s,,, y,,s,, + bpd,,s,,] ∩ [y,,e,,, y,,e,,
+ bpd,,e,,] ≠ ∅ ⇒ x,,s,, + ipd,,s,, < x,,e,,
-  4. y ≥ 0
-  5. ∀ side-float' ≺ side-float, y ≥ y'
-  ∀ block-area ≺ side-float, y,,side-float,, ≥ y,,block-area,,, where y,,block-area,,
is the y-coordinate of the before-edge of the block-area's border-rectangle minus the block-area's
space-before(.optimum?)
-  6.#6 ∀ line-area ≺ start-float, y ≥ y[before-edge of the line-area's allocation-rectangle]
-  7. ∃ start-float', [y, y + bpd] ∩ [y', y' + bpd'] ≠ ∅ ⇒ x + ipd ≤ ipd,,ref-area,,
-  8. y should be minimized
-  9. x should be minimized
-  10. if "clear" = "left", "start", "both", ∀ start-float' ≺ side-float, y > y' +
bpd'
-  if "clear" = "right", "end", "both", ∀ end-float' ≺ side-float, y > y' + bpd'
- 
- Here's a [http://atvaark.dyndns.org/~vincent/side-floats.pdf pdf version] for those whose
browser has difficulties displaying UTF-8 characters.
- 
- === Uncertainties ===
- At the beginning of section 9.5 of the CSS2 recommendation, it is loosely explained how
floats should be placed, and it is said that the precise placement rules should be found in
the description of the "float" property.
- 
- Two hints are given at this place, of which only one may be retrieved in the precise rules:
-  * the top of the floated box is aligned with the top of the current line box: this corresponds
to rule 6
-  * ... or bottom of the preceding block box if no line box exists.
- 
- This last point may occur in XSL-FO if the generated anchor area must be a block-area. AFAICT
there is no rule for it in the description of the "float" property. Rule 5 would even let
think that the top of the floated box should be aligned with the ''top'' of the previous block
box. Moreover, in the CSS 2.1 candidate recommendation this sentence doesn't appear anymore.
- 
- That said, I think the behavior that most users would expect is to align the float with
the bottom of the previous (non-floating) block box. This also is what is implemented by all
the browsers I've tested (Konqueror, Safari, Firefox). So I think we may implement it like
that too.
- 
- Another uncertainty is caused by the following sentence of section 9.5: "If there isn't
enough horizontal room on the current line for the float, it is shifted downward, line by
line, until a line has room for it." And what if the height of the float is less than the
line-height? Should it still be shifted one entire line downward? This sentence is in contradiction
with rule 8 (y should be minimized). In CSS 2.1 it has been rephrased such that "line by line"
doesn't appear anymore. So I think we may go with CSS 2.1.
- 
- Finally, may side-floats be split on several pages? There is nothing about that in the XSL-FO
spec. The chapter 13, "Page Media" of the CSS2 recommendation gives a small hint in section
13.3.6: we should "avoid breaking inside a floated element". If one uses side-floats to have
margin notes, one can reasonably expect them to be split on several pages. Therefore, if it
is simple enough to implement side-float breaking, I'll do it; if it involves too many changes
or a too complicated algorithm, I'll leave it for now (note that Xep does not break side-floats,
even if they are too big to fit on a page; they are simply discarded).
- 
- === Computing Intrusion-adjustments ===
- ==== Definitions ====
- Unless otherwise noted, the coordinates are those of the "start-before" vertex of the allocation-rectangle.
-  * Let A be a side-float, B a block-area with the same nearest ancestor reference-area;
-    A, B inline-overlapping ⇔ [y,,A,,, y,,A,, + bpd,,A,,] ∩ [y,,B,,, y,,B,, + border-before,,B,,
+ padding-before,,B,, + bpd,,B,, + padding-after,,B,, + border-after,,B,,] ≠ ∅
-  * Let A be a start-float, B a block-area with the same nearest ancestor reference-area;
-    A encroaches-upon B ⇔ A, B inline-overlapping ''and'' start-indent,,B,, < x,,A,,
+ ipd,,A,,
-    Then start-encroachment(A,B) = x,,A,, + ipd,,A,, - start-indent,,B,,
-  * Let A be an end-float, B a block-area with the same nearest ancestor reference-area;
-    A encroaches-upon B ⇔ A, B inline-overlapping ''and'' end-indent,,B,, < ipd,,A,,
+ end-indent,,A,,
-    Then end-encroachment(A,B) = ipd,,A,, + end-indent,,A,, - end-indent,,B,, = ipd,,ref-area,,
- x,,A,, - end-indent,,B,,
- 
- ==== Computation Rules ====
- Let F be a formatting object to which the "intrusion-displace" property applies. Then:
-  * if intrusion-displace = "none"
-    start-intrusion-adjustment = end-intrusion-adjustment = 0
- 
-  * if intrusion-displace = "line"
-   * for each generated block-area B which is not a line-area:
-   ||<|2>local-start-intrusion-adjustment =||0 if parent-area = ref-area||
-   ||start-intrusion-adjustment of parent-area, else||
-   Then start-intrusion-adjustment,,B,, = max(local-start-intrusion-adjustment,,B',,, B'
normal block-area generated and returned by F)
-   * for each generated line-area L
-   ||<|2>start-intrusion-adjustment = max||start-intrusion-adjustment(L parent)||
-   ||start-encroachment(A,L), A start-float such that A encroaches-upon L||
- 
-  * if intrusion-displace="indent"
-   * for each generated block-area B which is not a line-area:
-   ||<|2>local-start-intrusion-adjustment =||0 if parent-area = ref-area||
-   ||start-intrusion-adjustment of parent-area, else||
-   Then start-intrusion-adjustment,,B,, = max(local-start-intrusion-adjustment,,B',,, B'
normal block-area generated and returned by F)
-   * for each generated line-area L
-   ||<|6>start-intrusion-adjustment = max||||<(>start-intrusion-adjustment(L
parent)||
-   ||start-encroachment(A,L)||||<(>A start-float such that A encroaches-upon L||
-   ||<|4>start-encroachment(A,B')||A start-float such that A,L inline-overlapping||
-   ||B' block-area ancestor of L||
-   ||B' descendant of L nearest ancestor ref-area||
-   ||∃ L' line-area child of B', A encroaches-upon L'||
- 
-  * if intrusion-displace="block"
-   * for each generated block-area B which is not a line-area:
-   ||<|9>local-start-intrusion-adjustment = max||||<(>0||
-   ||start-intrusion-adjustment(B parent)||B parent is not a ref-area||
-   ||<|3(>start-encroachment(A,B)||A start-float||
-   ||generating-fo(A) is not a descendant of F||
-   ||∃ L' line-area child of B, A encroaches-upon L'||
-   ||<|4(>start-encroachment(A,B')||A start-float such that A,B inline-overlapping||
-   ||B' block-area ancestor of B||
-   ||B' descendant of B nearest ancestor ref-area||
-   ||∃ L line-area child of B', A encroaches-upon L||
-   Then start-intrusion-adjustment,,B,, = max(local-start-intrusion-adjustment,,B',,, B'
normal block-area generated and returned by F)
-   * for each generated line-area L
-   ||<|2>start-intrusion-adjustment = max||start-intrusion-adjustment(L parent)||
-   ||start-encroachment(A,L), A start-float such that A encroaches-upon L||
- 
- I'll first implement the "line" value, as this is probably the most expected by users. I'll
forget "block" and "indent" for now if after a quick look they turn out to be too complicated
to implement.
- 

---------------------------------------------------------------------
To unsubscribe, e-mail: fop-commits-unsubscribe@xmlgraphics.apache.org
For additional commands, e-mail: fop-commits-help@xmlgraphics.apache.org


Mime
View raw message