From 5f8de423f190bbb79a62f804151bc24824fa32d8 Mon Sep 17 00:00:00 2001 From: "Matt A. Tobin" Date: Fri, 2 Feb 2018 04:16:08 -0500 Subject: Add m-esr52 at 52.6.0 --- layout/doc/DD-SpaceManager.html | 743 ++++++++++++++++++++++++++++++++++++++++ 1 file changed, 743 insertions(+) create mode 100644 layout/doc/DD-SpaceManager.html (limited to 'layout/doc/DD-SpaceManager.html') diff --git a/layout/doc/DD-SpaceManager.html b/layout/doc/DD-SpaceManager.html new file mode 100644 index 000000000..39cd16597 --- /dev/null +++ b/layout/doc/DD-SpaceManager.html @@ -0,0 +1,743 @@ + + + + + + + + Detailed Design Template + + + +

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(nsIPresShell* 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(nsIPresShell* 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

+ + + + + + + + -- cgit v1.2.3