FOray Users
Module Users

FOray Development: AreaTree Design Notes


Comments on this page have more to do with goals than current reality.


Here are some introductory ideas that may help in understanding the AreaTree design:

  • Area sizes are computed and accumulated from the bottom up.
  • Area size constraints are imposed from the top down.
  • Area locations are dependent on Area sizes, but, except for that, are computed from the top down.
  • AreaTree handles all issues related to writing-mode and reference-orientation. Layout never has to know anything about them, but can work exclusively with the sizes of the areas to complete its work.


AreaTree is responsible to pass FOTree property values through, adding any parameters that are required to complete the computation. Because FOTree does not have all of the information that is required to compute values (like sizes of containing areas), it relies on input parameters for this information. AreaTree can provide this information automatically. Therefore the Layout system can usually get the computed values from the AreaTree without providing any parameters. To get the same value from the FOTree would require a parameter, which Layout would need to obtain from the AreaTree anyway.

Data Model

FOray has chosen to use an extremely lean data model for the AreaTree, tightly binding it to the FOTree contents. The other alternative would have been to make the AreaTree totally independent of the FOTree, essentially duplicating its content and traits. Here are the main reasons we chose to bind the AreaTree to the FOTree:

  • FOray needs to be able to handle both eager and patient layout systems. An eager layout system might conserve memory by creating an independent AreaTree and discarding as much of the FOTree as possible as it is finished with each piece of it. However, since a patient system needs to have access to an entire page-sequence at one time, such duplication will actually use much more memory.
  • AreaTree may need to eventually be able to respond to user-initiated GUI events and initiate processing in the FOTree or farther upstream. To do so requires a pointer back to FOTree.
  • The main advantage to using an independent AreaTree is to allow non-XSL-FO systems to use it. This is not currently important to FOray, and, if it ever did become important, we think that the proper approach would be to 1) extract two aXSL interfaces consistent with the current AreaTree, one each for input and output, 2) create a sister AreaTree system that implements the output interface (i.e. the interface that the Renderers use to convert an AreaTree to the proper output), and which duplicates the data, and 3) Create an adapter that converts the input written for the current AreaTree to instead actually create the new sisterArea Tree.

The main data actually stored in AreaTree is:

  • Parent and child relationships within the AreaTree itself.
  • The cross-reference between the FOTree generated-by object and its “child” AreaTree object(s).
  • A certain amount of resolved size information.


Each Area in the AreaTree is responsible to know its location on the page. The general plan is as follows. Each area type has a progression-dimension. For block areas (including line areas), this is the BPD. For inline areas, it is the IPD. Let us call the other dimension the layout-dimension (there may be a better term). In all cases, the layout-dimension is provided by the parent. The IPD of any block area comes from its parent, as does the BPD of any inline area. EveryArea must know its progression-dimension. This can conceivably be computed from its children, but should probably be cached for efficiency. If each Area knows this one piece of information, the location of every Area on the page can be computed. This is true because every Area has some ancestor that has a fixed location on the page. Through recursion, each Area computes its own location by first asking its parent for the parent's location on the page, and then accounting for the progression-dimension of all preceding siblings.


Legacy code uses DisplaySpace and InlineSpace classes to store the resolved values of block-spaces and inline-spaces. We think some efficiencies and clarities can be achieved by storing this value directly inside a content Area instead. Since there is theoretically no real need to consider spaces on the trailing edges (after and end) unless there is an area that actually is on that edge, we will store the resolved spaces of both the block and inline variety in the content area. This will always store, if you will, the "effective" before- or start-edge spacing. So, while both the before- or start-edge of an anterior, and the after- or end-edge of a posterior area must be considered in the computation, the computed value can be stored in the posterior area. With InlineSpace, the additional issues of text-decoration, eatability, and mutability can be addressed by the parent area.

fo:marker and fo:retrieve-marker

See the discussion of FOTree fo:marker and fo:retrieve-marker for background on the problem. The two main challenges on the AreaTree side of this issue are 1) handling the FOTree-AreaTree linkage ("generated-by", "is-first", etc.), and 2) being able to provide the correct RetrieveMarker instance to the FOTree when it is needed for inheritance reasons.

FOTree-AreaTree Linkage for fo:marker and fo:retrieve-marker

Recording the correct "generated-by" is not very difficult. The problem is with ordering the children, finding the first and last, etc. Since the same marker can actually be laid out multiple times, its descendants can be laid out multiple times as well, and you can't just treat all of them as part of the same family. This implies that the data must actually be copied, or at least that references to it must be copied.

The solution chose was to make FOLinkage abstract, and to have two subclasses, one (FOLinkageNormal) which tracks normal linkage (not inside an fo:marker), and the other (FOLinkageMarker) to track linkage for items inside a marker. The latter encapsulates a separate FOLinkageNormal instance for each fo:retrieve-marker for which the fo:marker content is grafted.

fo:retrieve-marker heritage

The solution to this problem is actually found in the solution to the linkage issue. The specialized linkage used for markers is keyed by the combination of the marker and retrieve-marker, and FOLinkageMarker has a method to retrieve the correct retrieve-marker for a given area whose generation heritiage is recorded therein.


  • Right now, leader-length is always computed relative to the IPD of its ancestor line-area, regardless of whether the line-area is the parent. Not sure this is right. Document after resolution.