GoogleSummerOfCode2006/ImplementingFloats

Google's Summer of Code Project Proposal: Implementing floats

This page is the draft of a project proposal that could be made at Google's Summer of Code. The goal is to gather the key points, the main issues and to sketch a timeline for the project.

Motivation

The project is to implement the fo:float formatting object in Fop. This element is used to generate two kinds of floats: before-floats for positioning objects in a separate area at the beginning of a page, and side-floats for positioning objects on one side of the page, with normal content flowing around it.

Before-floats are typically used to render figures, images, tables and so on. Such objects are frequent in book-like documents: they often carry additional information which is not required to understand the reading, and to which the reader may want to further refer. As Fop is often used as a print backend to render DocBook documents, many users would benefit from the implementation of before-floats.

Side-floats may be used to achieve various effects, such as drop capitals (displaying the first letter of a paragraph in a large size, spanning several lines of the paragraph), margin notes, illustrating images integrated in the content with text flowing around, etc.

Main Areas of Work

• validate the source file: there are several constraints on the usage of floats: they may not appear as children of other float or footnote elements, they must not be descendant of a flow which is not assigned to a region-body, etc.

• study whether the layout of floats may be readily expressed in the Knuth box-glue-penalty model, or if it has to be extended, and how...

• study how floats interfere with other fo elements (footnotes, absolutely positioned elements...), line- and page-breaking

• consider the possibility to apply different algorithms, especially regarding placement of before-floats (first-fit, best-fit, total-fit algorithm, performance and memory issues)

Proposed Goals

• complete implementation of before-floats, with at least two placement algorithms:

  • first-fit: fast, memory-efficient, low-quality

  • total-fit: slow, memory-consuming, high-quality

  it should be possible to choose the algorithm through a user-config option

• basic implementation of side-floats, working for the simplest cases. Examples of not-so-simple cases:

  • when many side-floats are to be placed and there is not enough room for a new one, or for the normal content

  • near page boundaries, when there is not enough room in the block-progression dimension to place the float

  The possible implementation difficulties should at least be identified, whith e.g. testcases illustrating special issues, to ease further work on this.

Schedule

1. Documentation phase: 1 month

   • XSL-FO and CSS specifications

   • Knuth glue-box-penalty and line-/page-breaking algorithm

   • Fop source code (Layout Managers)

2. Before-floats implementation: 3 weeks

   • algorithm

   • design choices

   • coding and testing

3. Side-floats implementation: 1 month and 1 week

   • understand and illustrate the computation of intrusion adjustments (this part of the spec looks rather complicated)

   • identify the typical layout situations

   • identify and document the trickiest cases

   • basic implementation