layout/doc/HLD-SpaceManager.html

   1 <!-- This Source Code Form is subject to the terms of the Mozilla Public
   2    - License, v. 2.0. If a copy of the MPL was not distributed with this
   3    - file, You can obtain one at http://mozilla.org/MPL/2.0/. -->
   4
   5 <!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
   6 <html>
   7 <head>
   8
   9   <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1">
  10   <title>Space Manager High Level Design</title>
  11   <meta name="author" content="Marc Attinasi (attinasi@netscape.com)">
  12 </head>
  13   <body>
  14
  15 <h1><font color="#cc0000">Gecko Layout High Level Design Document</font></h1>
  16
  17 <h1>Space Manager High Level Design</h1>
  18  <br>
  19
  20 <h2>Overview</h2>
  21   The Space Manager and associated classes and strructures are used by Block
  22 and Line layout to manage rectangular regions that are occupied and available,
  23 for correct handling of floated elements and the elements that flow around
  24 them. &nbsp;When elements are floated to the left or right in a layout, they
  25 take up space and influence where other elements can be placed. &nbsp;The
  26 Space Manager is responsible for keeping track of where space is taken up
  27 and where it is available. This information is used by block layout to correctly
  28 compute where other floated elements should be placed, and how much space
  29 is available to normal in-flow elements that flow around the floated bits.<br>
  30  <br>
  31   The Space Manager works in concert with several other classes to do its
  32 job. The classes that are considered part of the Space Manager are:<br>
  33
  34 <ul>
  35    <li>nsSpaceManager</li>
  36    <li>nsBandData</li>
  37    <li>nsBlockBandData</li>
  38    <li>BandRect / BandList (private structs)</li>
  39    <li>FrameInfo (private struct)</li>
  40    <li>nsBandtrapezoid</li>
  41
  42 </ul>
  43   Outside of the Space Manager itself, the clients of the Space Manager also
  44  play an inportant part in the management of he available and used space.
  45 &nbsp;The primary classes that interact with the Space Manager are:<br>
  46
  47 <ul>
  48    <li>nsBlockReflowState</li>
  49    <li>nsBlockFrame</li>
  50    <li>nsBoxToBlockAdaptor</li>
  51
  52 </ul>
  53   The general interaction model is to create a Space Manager for a block
  54 frame  in the context of a Reflow, and to associate it with the BlockReflowState
  55  so it is passed down to child frames' reflow methods. After reflow, the
  56 Space  Manager is destroyed. &nbsp;During reflow, the space manager stores
  57 the space  taken up by floats (UpdateSpaceManager in nsBlockFrame) and
  58 provides information  about the space available for other elements (GetAvailableSpace
  59 in nsBlockReflowState).  &nbsp;<br>
  60  <br>
  61  Additionally, there is a need to manage impacts to lines caused by
  62 changes to floated elements. &nbsp;This is referred to as Propagation
  63 of Float Damage and is handled by the Block Frame, making use of the
  64 Space Manager. When a float is incrementally reflowed, the Space
  65 Manager is notified if the float's region has changed. If so, the
  66 vertical space that has been affected (including both the float's old
  67 region and the float's new region) is noted in the internal
  68 nsIntervalSet as potential float damage (the method is
  69 IncludeInDamage).  During the incremental reflow of dirty lines the
  70 block frame may encounter lines that are NOT dirty. In this case the
  71 Space Manager is also asked if &nbsp;there is any float damage, and
  72 if there is then the block further checks to see if that damage
  73 intersects the area of the non-dirty line, marking it dirty if there
  74 is intersection. &nbsp;Thus, changes to floats on other lines may
  75 cause impact to otherwise clean lines, and the Space Manager
  76 facilitates the detection of this.  <h2>Data Model</h2>
  77
  78 <h4>Class/Component Diagram</h4>
  79
  80 <blockquote>
  81   <div align="Left"><img src="SpaceManagerClasses.png" alt="SpaceManager Class Diagram" idth="500" eight="459" title="Example Class Diagram">
  82    <br>
  83    </div>
  84    </blockquote>
  85
  86   <ul>
  87      <li>nsSpaceManager: The central point of management of the space taken
  88  up by floats in a block</li>
  89      <li>nsBandData: Provides information about the frames occupying a band
  90  of occupied or available space</li>
  91      <li>nsBlockBandData: A specialization of nsBandData that is used by
  92 nsBlockReflowState   to determine the available space, float impacts, and
  93 where floats are  cleared. &nbsp;Essentially a CSS-specific wrapper for
  94 generic nsBandData.</li>
  95      <li>BandRect: Keeps the bounds of a band, along with the frames associated
  96  with the band. &nbsp;BandRects are a linked list (provided by PRCListStr
  97 super-class) and also provide some geometry-management methods (SplitVertically,
  98 SplitHorizontally) and some methods that query or manipulate the frames associated
  99 with the band (IsOccupiedBy, AddFrame, RemoveFrame).</li>
 100      <li>BandList: A subclass of BandRect that provides a list interface
 101 -  Head(), Tail(), IsEmpty(), etc.</li>
 102      <li>FrameInfo: A structure that keeps information about the rectangle
 103  associated with a specific frame, in a linked list.</li>
 104      <li>nsBandTrapezoid: Represents the discrete regions within a band that
 105  are either Available, Occupied by a single frame, or Occupied by several
 106 frames. &nbsp;This is used to communicate information about the space in
 107 the band to the clients of the SpaceManager. &nbsp;There is no internal use
 108 of the nsBandTrapezoid by the Space Manager, rather it uses its internal
 109 BandList to create a BandData collection, which is largely made up of nsTrapezoid
 110 data.<br>
 111      </li>
 112
 113   </ul>
 114
 115   <h2>Use Case</h2>
 116
 117   <h4>Use Case 1: Space Manager is Created / Destroyed</h4>
 118   Space Manager instances are created in the nsBlockFrame's Reflow method.
 119  &nbsp;<br>
 120
 121   <ul>
 122      <li>An instance is created&nbsp;</li>
 123      <li>The BlockReflowState's previous Space Manager is saved off.</li>
 124      <li>The new Space Manager instance is associated with the BlockReflowState.
 125 &nbsp;</li>
 126      <li>After the block frame's Reflow has completed, the old Space Manager
 127 instance is re-associated with the BlockReflowState</li>
 128      <li>The new Space Manager is destroyed.</li>
 129
 130   </ul>
 131  If the BlockReflowState already had a Space Manager instance associated
 132 with  it, it is stored off before being replaced, and the returned to the
 133 BlockReflowState  instance after the new one has been destroyed. &nbsp;Thus,
 134 Space Managers  are effectively 'nested' during reflow, with each new block
 135 introducing its  own Space Manager.
 136
 137   <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
 138 floated  block may be added to it. &nbsp;This happens in the method <i>nsBlockReflowState::RecoverFloats</i> and
 139 <i>nsBlockReflowState::FlowAndPlaceFloat</i> (formerly this was done in nsBlockFrame::UpdateSpaceManager). &nbsp;<br>
 140 <br>
 141 The general algorightm in <i>nsBlockReflowState::RecoverFloats</i> is:<br>
 142
 143   <ul>
 144      <li>For each line in the block, see if it has floated blocks</li>
 145      <li>If floats are in the line, iterate over the floats and add each
 146  one to the Space Manager via the AddRectRegion method. &nbsp;The actual rect
 147  for the frame is cached in an nsFloatCache so it does not have to be recomputed.</li>
 148      <li>If the block has any block children, then translate the Space Manager
 149  to the child block's origin and update the space manager in the context
 150 for the child block, recursively. When done with the child, restore the Space
 151  Managers coordinates by translating by the negative of the child block's
 152 origin.&nbsp;       <br>
 153      </li>
 154
 155   </ul><br>
 156
 157 The general algorightm in <i>nsBlockReflowState::FlowAndPlaceFloat</i> is:<br>
 158 <ul>
 159   <li>The region that the float currently occupies is recorded.</li>
 160   <li>The band of available space is searched (with nsBlockReflowState::GetAvailableSpace);</li>
 161   <li>The float frame that is get from the passed nsFloatCache argument is reflowed
 162   and its rect is retrieved with GetRect;</li>
 163   <li>The floats margins are added;</li>
 164   <li>Check if the float can be placed in the acutal band: if not advance to the next band;</li>
 165   <li>Check the float type and if it can be added to the space manager;</li>
 166   <li>Align the float to its containing block top if rule
 167       <a href="http://www.w3.org/TR/REC-CSS2/visuren.html#float-position">CSS2/9.5.1/4</a>
 168       is not respected;</li>
 169   <li>Add the float using <i>nsSpaceManager::AddRectRegion</i> </li>
 170   <li>Compare the area that the float used to occupy with the area that it now occupies: if different,
 171       record the vertically affected interval using <i>nsSpaceManager::IncludeInDamage</i></li>
 172 </ul>
 173   <h4>Use Case 3: Space Manager is used to find available space to reflow
 174  into</h4>
 175   The nsBlockFrame makes use of the Space Manager indirectly to get the available
 176  space to reflow a child block or inline frame into. The block frame uses
 177 a helper method on the nsBlockReflowState class to do the actual computation
 178  of available space based on the data in the Space Manager. Here is how it
 179 works for reflowing an inline frame within a block (this also occurs for
 180 reflowing a block frame and, partially, for preparing for a resize reflow).<br>
 181
 182   <ul>
 183      <li>nsBlockFrame first frees all float information for the line that
 184  is being reflowed.</li>
 185      <li>GetAvailableSpace is called on the BlockReflowState</li>
 186      <li>the BlockReflowState calls GetAvailableSpace on its BlockBandData
 187  instance (which was setup in the BlockReflowState's constructor based on
 188 the SpaceManager passed in and computed content area).</li>
 189      <li>BlockBandData then gets the band data from the space manager via
 190 a call to the Space Manager associated with the BlockBandData instance.</li>
 191      <li>The BlockBandData then walks the collection of trapezoids that were
 192  returned by the SpaceManager method GetBandData (as nsBandData wrappers)
 193 and determines the right-most edge of the available space.</li>
 194      <li>The BlockReflowState then stores this available space rect for use
 195  in the rest of the reflow chain.<br>
 196      </li>
 197
 198   </ul>
 199
 200   <h4>Use Case 4: Propagation of Float Damage: detecting and handling float
 201 damage</h4>
 202   This process is driven by the Block Frame.<br>
 203
 204   <ul>
 205      <li>A non-dirty line is encountered by the Block Frame in ReflowDirtyLines</li>
 206      <li>Block Frame calls its PropagateFloatDamage method</li>
 207      <li>The Space Manager is checked to see if there is any float damage</li>
 208      <li>If there is, then the block frame asks the Space Manager if the
 209 line in question intersects the float damage</li>
 210      <li>If the line does intersect a damage interval, then the line is marked
 211 dirty</li>
 212      <li>If the line does not intersect a damage interval, it may still be
 213 marked dirty if:</li>
 214
 215     <ul>
 216        <li>it was impacted by floats before, but is not any longer</li>
 217        <li>it was not impacted by floats befre, but is now</li>
 218        <li><a name="block-line-impact"></a>
 219  it is impacted by floats and is a block<br>
 220        </li>
 221
 222     </ul>
 223
 224   </ul>
 225    <br>
 226
 227   <hr width="100%" size="2"><br>
 228
 229   <h1><font color="#ff0000">Problems / bugs found during documentation:</font></h1>
 230
 231   <ul>
 232      <li>BandRect and BandList are public in nsSpaceManager.h - should be
 233 private (compiles fine)</li>
 234      <li>nsSpaceManager data members are declared protected, but there are
 235  no subclasses. Should be private (compiles fine)</li>
 236      <li>nsBlockFrame::Paint is mucking with nsBlockBandData in and #if 0
 237 block - remove that and the include (compiles fine)</li>
 238      <li>nsSpaceManger has no way of clearing the float damage interval
 239 set - this might be needed if the SpaceManager persists beyond a Reflow</li>
 240   </ul>
 241    <br>
 242    <br>
 243
 244   </body>
 245   </html>