You are viewing a plain text version of this content. The canonical link for it is here.
Posted to fop-commits@xmlgraphics.apache.org by Apache Wiki <wi...@apache.org> on 2006/08/04 12:38:17 UTC
[Xmlgraphics-fop Wiki] Trivial Update of
"GoogleSummerOfCode2006/FloatsImplementationProgress" by VincentHennebert
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