Gecko Layout Detailed Design Document

Space Manager Detailed Design

Overview

The Space Manager and related classes and structures are an important of the Gecko Layout system, specifically Block Layout.  See the High Level Design document for an overview of the Space Manager, and as an introduction to the classes, structures and algorithms container in this, the Detailed Design Document.


nsSpaceManager

The Space Manager is the central class is a group of classes that manage the occupied and available space that exists in horizontal bands across a canvas.  The primary goal of the Space Manager is to provide information about those bands of space to support the CSS notion of floated elements.

There are three important parts to the Space Manager API: the parts that deal with the coordinate space of the Space Manager, the parts that deal with the regions managed by the Space Manager, and the parts that manage float impact intervals.

The class nsSpaceManager is declared in the file nsSpaceManger.h .  The class is only used in the layout module and cannot be exported outside of that module (nor does it need to be).  It is not a general purpose class, and is not intended to be subclasses .

Here is the class declaration, taken from the source file as of 01.08.02

/**
 * Class for dealing with bands of available space. The space manager
 * defines a coordinate space with an origin at (0, 0) that grows down
 * and to the right.
 */
class nsSpaceManager {
public:
  nsSpaceManager(PresShell* aPresShell, nsIFrame* aFrame);
  ~nsSpaceManager();

  void* operator new(size_t aSize);
  void operator delete(void* aPtr, size_t aSize);

  static void Shutdown();

  /*
   * Get the frame that's associated with the space manager. This frame
   * created the space manager, and the world coordinate space is
   * relative to this frame.
   *
   * You can use QueryInterface() on this frame to get any additional
   * interfaces.
   */
  nsIFrame* GetFrame() const { return mFrame; }

  /**
   * Translate the current origin by the specified (dx, dy). This
   * creates a new local coordinate space relative to the current
   * coordinate space.
   */
  void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }

  /**
   * Returns the current translation from local coordinate space to
   * world coordinate space. This represents the accumulated calls to
   * Translate().
   */
  void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }

  /**
   * Returns the y-most of the bottommost band or 0 if there are no bands.
   *
   * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
   */
  PRBool YMost(nscoord& aYMost) const;

  /**
   * Returns a band starting at the specified y-offset. The band data
   * indicates which parts of the band are available, and which parts
   * are unavailable
   *
   * The band data that is returned is in the coordinate space of the
   * local coordinate system.
   *
   * The local coordinate space origin, the y-offset, and the max size
   * describe a rectangle that's used to clip the underlying band of
   * available space, i.e.
   * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
   * coordinate space
   *
   * @param   aYOffset the y-offset of where the band begins. The coordinate is
   *            relative to the upper-left corner of the local coordinate space
   * @param   aMaxSize the size to use to constrain the band data
   * @param   aBandData [in,out] used to return the list of trapezoids that
   *            describe the available space and the unavailable space
   * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
   *            not large enough. The 'count' member of the band data struct
   *            indicates how large the array of trapezoids needs to be
   */
  nsresult GetBandData(nscoord       aYOffset,
                       const nsSize& aMaxSize,
                       nsBandData&   aBandData) const;

  /**
   * Add a rectangular region of unavailable space. The space is
   * relative to the local coordinate system.
   *
   * The region is tagged with a frame
   *
   * @param   aFrame the frame used to identify the region. Must not be NULL
   * @param   aUnavailableSpace the bounding rect of the unavailable space
   * @return  NS_OK if successful
   *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
   */
  nsresult AddRectRegion(nsIFrame*     aFrame,
                         const nsRect& aUnavailableSpace);

  /**
   * Resize the rectangular region associated with aFrame by the specified
   * deltas. The height change always applies to the bottom edge or the existing
   * rect. You specify whether the width change applies to the left or right edge
   *
   * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  enum AffectedEdge {LeftEdge, RightEdge};
  nsresult ResizeRectRegion(nsIFrame*    aFrame,
                            nscoord      aDeltaWidth,
                            nscoord      aDeltaHeight,
                            AffectedEdge aEdge = RightEdge);

  /**
   * Offset the region associated with aFrame by the specified amount.
   *
   * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);

  /**
   * Remove the region associated with aFrane.
   *
   * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  nsresult RemoveRegion(nsIFrame* aFrame);

  /**
   * Clears the list of regions representing the unavailable space.
   */
  void ClearRegions();

  /**
   * Methods for dealing with the propagation of float damage during
   * reflow.
   */
  PRBool HasFloatDamage()
  {
    return !mFloatDamage.IsEmpty();
  }

  void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
  {
    mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
  }

  PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
  {
    return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
  }

#ifdef DEBUG
  /**
   * Dump the state of the spacemanager out to a file
   */
  nsresult List(FILE* out);

  void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;
#endif

private:
  // Structure that maintains information about the region associated
  // with a particular frame
  struct FrameInfo {
    nsIFrame* const mFrame;
    nsRect          mRect;       // rectangular region
    FrameInfo*      mNext;

    FrameInfo(nsIFrame* aFrame, const nsRect& aRect);
#ifdef NS_BUILD_REFCNT_LOGGING
    ~FrameInfo();
#endif
  };

  // Doubly linked list of band rects
  struct BandRect : PRCListStr {
    nscoord   mLeft, mTop;
    nscoord   mRight, mBottom;
    int32_t   mNumFrames;    // number of frames occupying this rect
    union {
      nsIFrame*    mFrame;   // single frame occupying the space
      nsVoidArray* mFrames;  // list of frames occupying the space
    };

    BandRect(nscoord aLeft, nscoord aTop,
             nscoord aRight, nscoord aBottom,
             nsIFrame*);
    BandRect(nscoord aLeft, nscoord aTop,
             nscoord aRight, nscoord aBottom,
             nsVoidArray*);
    ~BandRect();

    // List operations
    BandRect* Next() const {return (BandRect*)PR_NEXT_LINK(this);}
    BandRect* Prev() const {return (BandRect*)PR_PREV_LINK(this);}
    void      InsertBefore(BandRect* aBandRect) {PR_INSERT_BEFORE(aBandRect, this);}
    void      InsertAfter(BandRect* aBandRect) {PR_INSERT_AFTER(aBandRect, this);}
    void      Remove() {PR_REMOVE_LINK(this);}

    // Split the band rect into two vertically, with this band rect becoming
    // the top part, and a new band rect being allocated and returned for the
    // bottom part
    //
    // Does not insert the new band rect into the linked list
    BandRect* SplitVertically(nscoord aBottom);

    // Split the band rect into two horizontally, with this band rect becoming
    // the left part, and a new band rect being allocated and returned for the
    // right part
    //
    // Does not insert the new band rect into the linked list
    BandRect* SplitHorizontally(nscoord aRight);

    // Accessor functions
    PRBool  IsOccupiedBy(const nsIFrame*) const;
    void    AddFrame(const nsIFrame*);
    void    RemoveFrame(const nsIFrame*);
    PRBool  HasSameFrameList(const BandRect* aBandRect) const;
    int32_t Length() const;
  };

  // Circular linked list of band rects
  struct BandList : BandRect {
    BandList();

    // Accessors
    PRBool    IsEmpty() const {return PR_CLIST_IS_EMPTY((PRCListStr*)this);}
    BandRect* Head() const {return (BandRect*)PR_LIST_HEAD(this);}
    BandRect* Tail() const {return (BandRect*)PR_LIST_TAIL(this);}

    // Operations
    void      Append(BandRect* aBandRect) {PR_APPEND_LINK(aBandRect, this);}

    // Remove and delete all the band rects in the list
    void      Clear();
  };


  FrameInfo* GetFrameInfoFor(nsIFrame* aFrame);
  FrameInfo* CreateFrameInfo(nsIFrame* aFrame, const nsRect& aRect);
  void       DestroyFrameInfo(FrameInfo*);

  void       ClearFrameInfo();
  void       ClearBandRects();

  BandRect*  GetNextBand(const BandRect* aBandRect) const;
  void       DivideBand(BandRect* aBand, nscoord aBottom);
  PRBool     CanJoinBands(BandRect* aBand, BandRect* aPrevBand);
  PRBool     JoinBands(BandRect* aBand, BandRect* aPrevBand);
  void       AddRectToBand(BandRect* aBand, BandRect* aBandRect);
  void       InsertBandRect(BandRect* aBandRect);

  nsresult   GetBandAvailableSpace(const BandRect* aBand,
                                   nscoord         aY,
                                   const nsSize&   aMaxSize,
                                   nsBandData&     aAvailableSpace) const;

  nsIFrame* const mFrame;     // frame associated with the space manager
  nscoord         mX, mY;     // translation from local to global coordinate space
  BandList        mBandList;  // header/sentinel for circular linked list of band rects
  FrameInfo*      mFrameInfoMap;
  nsIntervalSet   mFloatDamage;

  static int32_t sCachedSpaceManagerCount;
  static void* sCachedSpaceManagers[NS_SPACE_MANAGER_CACHE_SIZE];

  nsSpaceManager(const nsSpaceManager&);  // no implementation
  void operator=(const nsSpaceManager&);  // no implementation
};

Public API

Life Cycle:

The Constructor requires a Presentation Shell, used for arena allocations mostly, and a frame that this Space Manager is rooted on.  The coordinate space of this Space Manager is relative to the frame passed in to the constructor.

  nsSpaceManager(PresShell* aPresShell, nsIFrame* aFrame);
  ~nsSpaceManager();

Operators 'new' and 'delete' are overridden to support a recycler.  Space Manager instances come and go pretty frequently, and this recycler prevents excessive heap allocations and the performance penalties associated with it. The #define NS_SPACE_MANAGER_CACHE_SIZE is used to control the number of Space Manager instances that can be present in the recycler, currently 4.  If more than NS_SPACE_MANAGER_CACHE_SIZE are allocated at a time, then standard allocation is used.

  void* operator new(size_t aSize);
  void operator delete(void* aPtr, size_t aSize);

A Static method is used to shutdown the Space Manager recycling.  This method deletes all of the Space Mangers inthe recycler,and prevents further recycling.  It is meant to be called only when the layout module is being terminated.

  static void Shutdown();

Origin / Coordinate Space Translation

  /**
   * Translate the current origin by the specified (dx, dy). This
   * creates a new local coordinate space relative to the current
   * coordinate space.
   */
  void Translate(nscoord aDx, nscoord aDy) { mX += aDx; mY += aDy; }

  /**
   * Returns the current translation from local coordinate space to
   * world coordinate space. This represents the accumulated calls to
   * Translate().
   */
  void GetTranslation(nscoord& aX, nscoord& aY) const { aX = mX; aY = mY; }

  /**
   * Returns the y-most of the bottommost band or 0 if there are no bands.
   *
   * @return  PR_TRUE if there are bands and PR_FALSE if there are no bands
   */
  PRBool YMost(nscoord& aYMost) const;

Region Management

  /**
   * Returns a band starting at the specified y-offset. The band data
   * indicates which parts of the band are available, and which parts
   * are unavailable
   *
   * The band data that is returned is in the coordinate space of the
   * local coordinate system.
   *
   * The local coordinate space origin, the y-offset, and the max size
   * describe a rectangle that's used to clip the underlying band of
   * available space, i.e.
   * {0, aYOffset, aMaxSize.width, aMaxSize.height} in the local
   * coordinate space
   *
   * @param   aYOffset the y-offset of where the band begins. The coordinate is
   *            relative to the upper-left corner of the local coordinate space
   * @param   aMaxSize the size to use to constrain the band data
   * @param   aBandData [in,out] used to return the list of trapezoids that
   *            describe the available space and the unavailable space
   * @return  NS_OK if successful and NS_ERROR_FAILURE if the band data is not
   *            not large enough. The 'count' member of the band data struct
   *            indicates how large the array of trapezoids needs to be
   */
  nsresult GetBandData(nscoord       aYOffset,
                       const nsSize& aMaxSize,
                       nsBandData&   aBandData) const;

  /**
   * Add a rectangular region of unavailable space. The space is
   * relative to the local coordinate system.
   *
   * The region is tagged with a frame
   *
   * @param   aFrame the frame used to identify the region. Must not be NULL
   * @param   aUnavailableSpace the bounding rect of the unavailable space
   * @return  NS_OK if successful
   *          NS_ERROR_FAILURE if there is already a region tagged with aFrame
   */
  nsresult AddRectRegion(nsIFrame*     aFrame,
                         const nsRect& aUnavailableSpace);

  /**
   * Resize the rectangular region associated with aFrame by the specified
   * deltas. The height change always applies to the bottom edge or the existing
   * rect. You specify whether the width change applies to the left or right edge
   *
   * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  enum AffectedEdge {LeftEdge, RightEdge};
  nsresult ResizeRectRegion(nsIFrame*    aFrame,
                            nscoord      aDeltaWidth,
                            nscoord      aDeltaHeight,
                            AffectedEdge aEdge = RightEdge);

  /**
   * Offset the region associated with aFrame by the specified amount.
   *
   * Returns NS_OK if successful, NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  nsresult OffsetRegion(nsIFrame* aFrame, nscoord dx, nscoord dy);

  /**
   * Remove the region associated with aFrane.
   *
   * Returns NS_OK if successful and NS_ERROR_INVALID_ARG if there is no region
   * tagged with aFrame
   */
  nsresult RemoveRegion(nsIFrame* aFrame);

  /**
   * Clears the list of regions representing the unavailable space.
   */
  void ClearRegions();

Float Impact

  /**
   * Methods for dealing with the propagation of float damage during
   * reflow.
   */
  PRBool HasFloatDamage()
  {
    return !mFloatDamage.IsEmpty();
  }

  void IncludeInDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
  {
    mFloatDamage.IncludeInterval(aIntervalBegin + mY, aIntervalEnd + mY);
  }

  PRBool IntersectsDamage(nscoord aIntervalBegin, nscoord aIntervalEnd)
  {
    return mFloatDamage.Intersects(aIntervalBegin + mY, aIntervalEnd + mY);
  }

Debug Only Methods

  /**
   * Dump the state of the spacemanager out to a file
   */
  nsresult List(FILE* out);

  void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const;

Unused / Obsolete Methods

  /*
   * Get the frame that's associated with the space manager. This frame
   * created the space manager, and the world coordinate space is
   * relative to this frame.
   *
   * You can use QueryInterface() on this frame to get any additional
   * interfaces.
   */
   nsIFrame* GetFrame() const { return mFrame; }

Implementation Notes

Algorithm 1: GetBandData

GetBandData is used to provide information to clients about what space if available and unavailable in a band of space.  The client provides a vertical offset, the yOffset, that corresponds to the band that is of interest.  This will be the y offset of the frame that is being reflowed.  The caller also provides a collection of BandData objects (an array) and the number of items that the collection can handle.  If the collection is too small, then an error is returned and the count is updated to indicate the size required.

The algorithm to provide the band data is as follows:

GetBandAvailableSpace:
This method is called from GetBandData only. It walks all of the bands in the space manager and determines which bands intersect with the band passed in, and if within those bands there are regions that are available or occupied.

Algorithm 2: AddRectRegion

Clients call into this method to notify the Space Manager that a new frame is occupying some space.
InsertBandRect:
Internal method to insert a band rect into the BandList in the correct location. There are several cases it has to handle, as specified in the source file comments:
// When comparing a rect to a band there are seven cases to consider.
// 'R' is the rect and 'B' is the band.
//
//      Case 1              Case 2              Case 3              Case 4
//      ------              ------              ------              ------
// +-----+             +-----+                      +-----+             +-----+
// |  R  |             |  R  |  +-----+    +-----+  |     |             |     |
// +-----+             +-----+  |     |    |  R  |  |  B  |             |  B  |
//          +-----+             |  B  |    +-----+  |     |    +-----+  |     |
//          |     |             |     |             +-----+    |  R  |  +-----+
//          |  B  |             +-----+                        +-----+
//          |     |
//          +-----+
//
//
//
//      Case 5              Case 6              Case 7
//      ------              ------              ------
//          +-----+    +-----+  +-----+    +-----+
//          |     |    |  R  |  |  B  |    |     |  +-----+
//          |  B  |    +-----+  +-----+    |  R  |  |  B  |
//          |     |                        |     |  +-----+
//          +-----+                        +-----+
// +-----+
// |  R  |
// +-----+
//
This algorithm is pretty confusing - basically what needs to happen is that rects and bands need to be divided up so that complicated cases like #2, #4, and #7, are reduced to simpler cases where the rects is totally above, below, or between a band rect.  From the current implementation, it might be worth verifying that the final result of the inserts is a correctly ordered liest of bandRects (debug mode only).

Algorithm 3: RemoveRegion

When a float is removed, the Space Manager is notified by a call to RemoveRegion, passing in the frame that is being removed.

Cross-Component Algorithms



Tech Notes