1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/layout/doc/HLD-SpaceManager.html Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,245 @@
1.4 +<!-- This Source Code Form is subject to the terms of the Mozilla Public
1.5 + - License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
1.7 +
1.8 +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
1.9 +<html>
1.10 +<head>
1.11 +
1.12 + <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
1.13 + <title>Space Manager High Level Design</title>
1.14 + <meta name="author" content="Marc Attinasi (attinasi@netscape.com)">
1.15 +</head>
1.16 + <body>
1.17 +
1.18 +<h1><font color="#cc0000">Gecko Layout High Level Design Document</font></h1>
1.19 +
1.20 +<h1>Space Manager High Level Design</h1>
1.21 + <br>
1.22 +
1.23 +<h2>Overview</h2>
1.24 + The Space Manager and associated classes and strructures are used by Block
1.25 +and Line layout to manage rectangular regions that are occupied and available,
1.26 +for correct handling of floated elements and the elements that flow around
1.27 +them. When elements are floated to the left or right in a layout, they
1.28 +take up space and influence where other elements can be placed. The
1.29 +Space Manager is responsible for keeping track of where space is taken up
1.30 +and where it is available. This information is used by block layout to correctly
1.31 +compute where other floated elements should be placed, and how much space
1.32 +is available to normal in-flow elements that flow around the floated bits.<br>
1.33 + <br>
1.34 + The Space Manager works in concert with several other classes to do its
1.35 +job. The classes that are considered part of the Space Manager are:<br>
1.36 +
1.37 +<ul>
1.38 + <li>nsSpaceManager</li>
1.39 + <li>nsBandData</li>
1.40 + <li>nsBlockBandData</li>
1.41 + <li>BandRect / BandList (private structs)</li>
1.42 + <li>FrameInfo (private struct)</li>
1.43 + <li>nsBandtrapezoid</li>
1.44 +
1.45 +</ul>
1.46 + Outside of the Space Manager itself, the clients of the Space Manager also
1.47 + play an inportant part in the management of he available and used space.
1.48 + The primary classes that interact with the Space Manager are:<br>
1.49 +
1.50 +<ul>
1.51 + <li>nsBlockReflowState</li>
1.52 + <li>nsBlockFrame</li>
1.53 + <li>nsBoxToBlockAdaptor</li>
1.54 +
1.55 +</ul>
1.56 + The general interaction model is to create a Space Manager for a block
1.57 +frame in the context of a Reflow, and to associate it with the BlockReflowState
1.58 + so it is passed down to child frames' reflow methods. After reflow, the
1.59 +Space Manager is destroyed. During reflow, the space manager stores
1.60 +the space taken up by floats (UpdateSpaceManager in nsBlockFrame) and
1.61 +provides information about the space available for other elements (GetAvailableSpace
1.62 +in nsBlockReflowState). <br>
1.63 + <br>
1.64 + Additionally, there is a need to manage impacts to lines caused by
1.65 +changes to floated elements. This is referred to as Propagation
1.66 +of Float Damage and is handled by the Block Frame, making use of the
1.67 +Space Manager. When a float is incrementally reflowed, the Space
1.68 +Manager is notified if the float's region has changed. If so, the
1.69 +vertical space that has been affected (including both the float's old
1.70 +region and the float's new region) is noted in the internal
1.71 +nsIntervalSet as potential float damage (the method is
1.72 +IncludeInDamage). During the incremental reflow of dirty lines the
1.73 +block frame may encounter lines that are NOT dirty. In this case the
1.74 +Space Manager is also asked if there is any float damage, and
1.75 +if there is then the block further checks to see if that damage
1.76 +intersects the area of the non-dirty line, marking it dirty if there
1.77 +is intersection. Thus, changes to floats on other lines may
1.78 +cause impact to otherwise clean lines, and the Space Manager
1.79 +facilitates the detection of this. <h2>Data Model</h2>
1.80 +
1.81 +<h4>Class/Component Diagram</h4>
1.82 +
1.83 +<blockquote>
1.84 + <div align="Left"><img src="SpaceManagerClasses.png" alt="SpaceManager Class Diagram" idth="500" eight="459" title="Example Class Diagram">
1.85 + <br>
1.86 + </div>
1.87 + </blockquote>
1.88 +
1.89 + <ul>
1.90 + <li>nsSpaceManager: The central point of management of the space taken
1.91 + up by floats in a block</li>
1.92 + <li>nsBandData: Provides information about the frames occupying a band
1.93 + of occupied or available space</li>
1.94 + <li>nsBlockBandData: A specialization of nsBandData that is used by
1.95 +nsBlockReflowState to determine the available space, float impacts, and
1.96 +where floats are cleared. Essentially a CSS-specific wrapper for
1.97 +generic nsBandData.</li>
1.98 + <li>BandRect: Keeps the bounds of a band, along with the frames associated
1.99 + with the band. BandRects are a linked list (provided by PRCListStr
1.100 +super-class) and also provide some geometry-management methods (SplitVertically,
1.101 +SplitHorizontally) and some methods that query or manipulate the frames associated
1.102 +with the band (IsOccupiedBy, AddFrame, RemoveFrame).</li>
1.103 + <li>BandList: A subclass of BandRect that provides a list interface
1.104 +- Head(), Tail(), IsEmpty(), etc.</li>
1.105 + <li>FrameInfo: A structure that keeps information about the rectangle
1.106 + associated with a specific frame, in a linked list.</li>
1.107 + <li>nsBandTrapezoid: Represents the discrete regions within a band that
1.108 + are either Available, Occupied by a single frame, or Occupied by several
1.109 +frames. This is used to communicate information about the space in
1.110 +the band to the clients of the SpaceManager. There is no internal use
1.111 +of the nsBandTrapezoid by the Space Manager, rather it uses its internal
1.112 +BandList to create a BandData collection, which is largely made up of nsTrapezoid
1.113 +data.<br>
1.114 + </li>
1.115 +
1.116 + </ul>
1.117 +
1.118 + <h2>Use Case</h2>
1.119 +
1.120 + <h4>Use Case 1: Space Manager is Created / Destroyed</h4>
1.121 + Space Manager instances are created in the nsBlockFrame's Reflow method.
1.122 + <br>
1.123 +
1.124 + <ul>
1.125 + <li>An instance is created </li>
1.126 + <li>The BlockReflowState's previous Space Manager is saved off.</li>
1.127 + <li>The new Space Manager instance is associated with the BlockReflowState.
1.128 + </li>
1.129 + <li>After the block frame's Reflow has completed, the old Space Manager
1.130 +instance is re-associated with the BlockReflowState</li>
1.131 + <li>The new Space Manager is destroyed.</li>
1.132 +
1.133 + </ul>
1.134 + If the BlockReflowState already had a Space Manager instance associated
1.135 +with it, it is stored off before being replaced, and the returned to the
1.136 +BlockReflowState instance after the new one has been destroyed. Thus,
1.137 +Space Managers are effectively 'nested' during reflow, with each new block
1.138 +introducing its own Space Manager.
1.139 +
1.140 + <h4>Use Case 2: Float is added to the Space Manager</h4> After a Space Manager is created for a block context's reflow chain, a
1.141 +floated block may be added to it. This happens in the method <i>nsBlockReflowState::RecoverFloats</i> and
1.142 +<i>nsBlockReflowState::FlowAndPlaceFloat</i> (formerly this was done in nsBlockFrame::UpdateSpaceManager). <br>
1.143 +<br>
1.144 +The general algorightm in <i>nsBlockReflowState::RecoverFloats</i> is:<br>
1.145 +
1.146 + <ul>
1.147 + <li>For each line in the block, see if it has floated blocks</li>
1.148 + <li>If floats are in the line, iterate over the floats and add each
1.149 + one to the Space Manager via the AddRectRegion method. The actual rect
1.150 + for the frame is cached in an nsFloatCache so it does not have to be recomputed.</li>
1.151 + <li>If the block has any block children, then translate the Space Manager
1.152 + to the child block's origin and update the space manager in the context
1.153 +for the child block, recursively. When done with the child, restore the Space
1.154 + Managers coordinates by translating by the negative of the child block's
1.155 +origin. <br>
1.156 + </li>
1.157 +
1.158 + </ul><br>
1.159 +
1.160 +The general algorightm in <i>nsBlockReflowState::FlowAndPlaceFloat</i> is:<br>
1.161 +<ul>
1.162 + <li>The region that the float currently occupies is recorded.</li>
1.163 + <li>The band of available space is searched (with nsBlockReflowState::GetAvailableSpace);</li>
1.164 + <li>The float frame that is get from the passed nsFloatCache argument is reflowed
1.165 + and its rect is retrieved with GetRect;</li>
1.166 + <li>The floats margins are added;</li>
1.167 + <li>Check if the float can be placed in the acutal band: if not advance to the next band;</li>
1.168 + <li>Check the float type and if it can be added to the space manager;</li>
1.169 + <li>Align the float to its containing block top if rule
1.170 + <a href="http://www.w3.org/TR/REC-CSS2/visuren.html#float-position">CSS2/9.5.1/4</a>
1.171 + is not respected;</li>
1.172 + <li>Add the float using <i>nsSpaceManager::AddRectRegion</i> </li>
1.173 + <li>Compare the area that the float used to occupy with the area that it now occupies: if different,
1.174 + record the vertically affected interval using <i>nsSpaceManager::IncludeInDamage</i></li>
1.175 +</ul>
1.176 + <h4>Use Case 3: Space Manager is used to find available space to reflow
1.177 + into</h4>
1.178 + The nsBlockFrame makes use of the Space Manager indirectly to get the available
1.179 + space to reflow a child block or inline frame into. The block frame uses
1.180 +a helper method on the nsBlockReflowState class to do the actual computation
1.181 + of available space based on the data in the Space Manager. Here is how it
1.182 +works for reflowing an inline frame within a block (this also occurs for
1.183 +reflowing a block frame and, partially, for preparing for a resize reflow).<br>
1.184 +
1.185 + <ul>
1.186 + <li>nsBlockFrame first frees all float information for the line that
1.187 + is being reflowed.</li>
1.188 + <li>GetAvailableSpace is called on the BlockReflowState</li>
1.189 + <li>the BlockReflowState calls GetAvailableSpace on its BlockBandData
1.190 + instance (which was setup in the BlockReflowState's constructor based on
1.191 +the SpaceManager passed in and computed content area).</li>
1.192 + <li>BlockBandData then gets the band data from the space manager via
1.193 +a call to the Space Manager associated with the BlockBandData instance.</li>
1.194 + <li>The BlockBandData then walks the collection of trapezoids that were
1.195 + returned by the SpaceManager method GetBandData (as nsBandData wrappers)
1.196 +and determines the right-most edge of the available space.</li>
1.197 + <li>The BlockReflowState then stores this available space rect for use
1.198 + in the rest of the reflow chain.<br>
1.199 + </li>
1.200 +
1.201 + </ul>
1.202 +
1.203 + <h4>Use Case 4: Propagation of Float Damage: detecting and handling float
1.204 +damage</h4>
1.205 + This process is driven by the Block Frame.<br>
1.206 +
1.207 + <ul>
1.208 + <li>A non-dirty line is encountered by the Block Frame in ReflowDirtyLines</li>
1.209 + <li>Block Frame calls its PropagateFloatDamage method</li>
1.210 + <li>The Space Manager is checked to see if there is any float damage</li>
1.211 + <li>If there is, then the block frame asks the Space Manager if the
1.212 +line in question intersects the float damage</li>
1.213 + <li>If the line does intersect a damage interval, then the line is marked
1.214 +dirty</li>
1.215 + <li>If the line does not intersect a damage interval, it may still be
1.216 +marked dirty if:</li>
1.217 +
1.218 + <ul>
1.219 + <li>it was impacted by floats before, but is not any longer</li>
1.220 + <li>it was not impacted by floats befre, but is now</li>
1.221 + <li><a name="block-line-impact"></a>
1.222 + it is impacted by floats and is a block<br>
1.223 + </li>
1.224 +
1.225 + </ul>
1.226 +
1.227 + </ul>
1.228 + <br>
1.229 +
1.230 + <hr width="100%" size="2"><br>
1.231 +
1.232 + <h1><font color="#ff0000">Problems / bugs found during documentation:</font></h1>
1.233 +
1.234 + <ul>
1.235 + <li>BandRect and BandList are public in nsSpaceManager.h - should be
1.236 +private (compiles fine)</li>
1.237 + <li>nsSpaceManager data members are declared protected, but there are
1.238 + no subclasses. Should be private (compiles fine)</li>
1.239 + <li>nsBlockFrame::Paint is mucking with nsBlockBandData in and #if 0
1.240 +block - remove that and the include (compiles fine)</li>
1.241 + <li>nsSpaceManger has no way of clearing the float damage interval
1.242 +set - this might be needed if the SpaceManager persists beyond a Reflow</li>
1.243 + </ul>
1.244 + <br>
1.245 + <br>
1.246 +
1.247 + </body>
1.248 + </html>
