michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: michael@0: Space Manager High Level Design michael@0: michael@0: michael@0: michael@0: michael@0:

Gecko Layout High Level Design Document

michael@0: michael@0:

Space Manager High Level Design

michael@0:
michael@0: michael@0:

Overview

michael@0: The Space Manager and associated classes and strructures are used by Block michael@0: and Line layout to manage rectangular regions that are occupied and available, michael@0: for correct handling of floated elements and the elements that flow around michael@0: them. When elements are floated to the left or right in a layout, they michael@0: take up space and influence where other elements can be placed. The michael@0: Space Manager is responsible for keeping track of where space is taken up michael@0: and where it is available. This information is used by block layout to correctly michael@0: compute where other floated elements should be placed, and how much space michael@0: is available to normal in-flow elements that flow around the floated bits.
michael@0:
michael@0: The Space Manager works in concert with several other classes to do its michael@0: job. The classes that are considered part of the Space Manager are:
michael@0: michael@0:

nsSpaceManager
nsBandData
nsBlockBandData
BandRect / BandList (private structs)
FrameInfo (private struct)
nsBandtrapezoid

michael@0: Outside of the Space Manager itself, the clients of the Space Manager also michael@0: play an inportant part in the management of he available and used space. michael@0: The primary classes that interact with the Space Manager are:
michael@0: michael@0:

nsBlockReflowState
nsBlockFrame
nsBoxToBlockAdaptor

michael@0: The general interaction model is to create a Space Manager for a block michael@0: frame in the context of a Reflow, and to associate it with the BlockReflowState michael@0: so it is passed down to child frames' reflow methods. After reflow, the michael@0: Space Manager is destroyed. During reflow, the space manager stores michael@0: the space taken up by floats (UpdateSpaceManager in nsBlockFrame) and michael@0: provides information about the space available for other elements (GetAvailableSpace michael@0: in nsBlockReflowState).
michael@0:
michael@0: Additionally, there is a need to manage impacts to lines caused by michael@0: changes to floated elements. This is referred to as Propagation michael@0: of Float Damage and is handled by the Block Frame, making use of the michael@0: Space Manager. When a float is incrementally reflowed, the Space michael@0: Manager is notified if the float's region has changed. If so, the michael@0: vertical space that has been affected (including both the float's old michael@0: region and the float's new region) is noted in the internal michael@0: nsIntervalSet as potential float damage (the method is michael@0: IncludeInDamage). During the incremental reflow of dirty lines the michael@0: block frame may encounter lines that are NOT dirty. In this case the michael@0: Space Manager is also asked if there is any float damage, and michael@0: if there is then the block further checks to see if that damage michael@0: intersects the area of the non-dirty line, marking it dirty if there michael@0: is intersection. Thus, changes to floats on other lines may michael@0: cause impact to otherwise clean lines, and the Space Manager michael@0: facilitates the detection of this.

Data Model

michael@0: michael@0:

Class/Component Diagram

michael@0: michael@0:

michael@0:
michael@0:
michael@0:
michael@0:

michael@0: michael@0:

nsSpaceManager: The central point of management of the space taken michael@0: up by floats in a block
nsBandData: Provides information about the frames occupying a band michael@0: of occupied or available space
nsBlockBandData: A specialization of nsBandData that is used by michael@0: nsBlockReflowState to determine the available space, float impacts, and michael@0: where floats are cleared. Essentially a CSS-specific wrapper for michael@0: generic nsBandData.
BandRect: Keeps the bounds of a band, along with the frames associated michael@0: with the band. BandRects are a linked list (provided by PRCListStr michael@0: super-class) and also provide some geometry-management methods (SplitVertically, michael@0: SplitHorizontally) and some methods that query or manipulate the frames associated michael@0: with the band (IsOccupiedBy, AddFrame, RemoveFrame).
BandList: A subclass of BandRect that provides a list interface michael@0: - Head(), Tail(), IsEmpty(), etc.
FrameInfo: A structure that keeps information about the rectangle michael@0: associated with a specific frame, in a linked list.
nsBandTrapezoid: Represents the discrete regions within a band that michael@0: are either Available, Occupied by a single frame, or Occupied by several michael@0: frames. This is used to communicate information about the space in michael@0: the band to the clients of the SpaceManager. There is no internal use michael@0: of the nsBandTrapezoid by the Space Manager, rather it uses its internal michael@0: BandList to create a BandData collection, which is largely made up of nsTrapezoid michael@0: data.
michael@0:

michael@0: michael@0:

Use Case

michael@0: michael@0:

Use Case 1: Space Manager is Created / Destroyed

michael@0: Space Manager instances are created in the nsBlockFrame's Reflow method. michael@0:
michael@0: michael@0:

An instance is created
The BlockReflowState's previous Space Manager is saved off.
The new Space Manager instance is associated with the BlockReflowState. michael@0:
After the block frame's Reflow has completed, the old Space Manager michael@0: instance is re-associated with the BlockReflowState
The new Space Manager is destroyed.

michael@0: If the BlockReflowState already had a Space Manager instance associated michael@0: with it, it is stored off before being replaced, and the returned to the michael@0: BlockReflowState instance after the new one has been destroyed. Thus, michael@0: Space Managers are effectively 'nested' during reflow, with each new block michael@0: introducing its own Space Manager. michael@0: michael@0:

Use Case 2: Float is added to the Space Manager

After a Space Manager is created for a block context's reflow chain, a michael@0: floated block may be added to it. This happens in the method nsBlockReflowState::RecoverFloats and michael@0: nsBlockReflowState::FlowAndPlaceFloat (formerly this was done in nsBlockFrame::UpdateSpaceManager).
michael@0:
michael@0: The general algorightm in nsBlockReflowState::RecoverFloats is:
michael@0: michael@0:

For each line in the block, see if it has floated blocks
If floats are in the line, iterate over the floats and add each michael@0: one to the Space Manager via the AddRectRegion method. The actual rect michael@0: for the frame is cached in an nsFloatCache so it does not have to be recomputed.
If the block has any block children, then translate the Space Manager michael@0: to the child block's origin and update the space manager in the context michael@0: for the child block, recursively. When done with the child, restore the Space michael@0: Managers coordinates by translating by the negative of the child block's michael@0: origin.
michael@0:

michael@0: michael@0: The general algorightm in nsBlockReflowState::FlowAndPlaceFloat is:
michael@0:

The region that the float currently occupies is recorded.
The band of available space is searched (with nsBlockReflowState::GetAvailableSpace);
The float frame that is get from the passed nsFloatCache argument is reflowed michael@0: and its rect is retrieved with GetRect;
The floats margins are added;
Check if the float can be placed in the acutal band: if not advance to the next band;
Check the float type and if it can be added to the space manager;
Align the float to its containing block top if rule michael@0: CSS2/9.5.1/4 michael@0: is not respected;
Add the float using nsSpaceManager::AddRectRegion
Compare the area that the float used to occupy with the area that it now occupies: if different, michael@0: record the vertically affected interval using nsSpaceManager::IncludeInDamage

michael@0:

Use Case 3: Space Manager is used to find available space to reflow michael@0: into

michael@0: The nsBlockFrame makes use of the Space Manager indirectly to get the available michael@0: space to reflow a child block or inline frame into. The block frame uses michael@0: a helper method on the nsBlockReflowState class to do the actual computation michael@0: of available space based on the data in the Space Manager. Here is how it michael@0: works for reflowing an inline frame within a block (this also occurs for michael@0: reflowing a block frame and, partially, for preparing for a resize reflow).
michael@0: michael@0:

nsBlockFrame first frees all float information for the line that michael@0: is being reflowed.
GetAvailableSpace is called on the BlockReflowState
the BlockReflowState calls GetAvailableSpace on its BlockBandData michael@0: instance (which was setup in the BlockReflowState's constructor based on michael@0: the SpaceManager passed in and computed content area).
BlockBandData then gets the band data from the space manager via michael@0: a call to the Space Manager associated with the BlockBandData instance.
The BlockBandData then walks the collection of trapezoids that were michael@0: returned by the SpaceManager method GetBandData (as nsBandData wrappers) michael@0: and determines the right-most edge of the available space.
The BlockReflowState then stores this available space rect for use michael@0: in the rest of the reflow chain.
michael@0:

michael@0: michael@0:

Use Case 4: Propagation of Float Damage: detecting and handling float michael@0: damage

michael@0: This process is driven by the Block Frame.
michael@0: michael@0:

A non-dirty line is encountered by the Block Frame in ReflowDirtyLines
Block Frame calls its PropagateFloatDamage method
The Space Manager is checked to see if there is any float damage
If there is, then the block frame asks the Space Manager if the michael@0: line in question intersects the float damage
If the line does intersect a damage interval, then the line is marked michael@0: dirty
If the line does not intersect a damage interval, it may still be michael@0: marked dirty if:

it was impacted by floats before, but is not any longer
it was not impacted by floats befre, but is now
michael@0: it is impacted by floats and is a block
michael@0:

michael@0:
michael@0: michael@0:

michael@0: michael@0:

Problems / bugs found during documentation:

michael@0: michael@0:

BandRect and BandList are public in nsSpaceManager.h - should be michael@0: private (compiles fine)
nsSpaceManager data members are declared protected, but there are michael@0: no subclasses. Should be private (compiles fine)
nsBlockFrame::Paint is mucking with nsBlockBandData in and #if 0 michael@0: block - remove that and the include (compiles fine)
nsSpaceManger has no way of clearing the float damage interval michael@0: set - this might be needed if the SpaceManager persists beyond a Reflow

michael@0:
michael@0:
michael@0: michael@0: michael@0: