diff options
Diffstat (limited to 'layout/doc/DD-SpaceManager.html')
| -rw-r--r-- | layout/doc/DD-SpaceManager.html | 743 |
1 files changed, 743 insertions, 0 deletions
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 @@ +<!-- This Source Code Form is subject to the terms of the Mozilla Public + - License, v. 2.0. If a copy of the MPL was not distributed with this + - file, You can obtain one at http://mozilla.org/MPL/2.0/. --> + +<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"> +<html> +<head> + + <meta http-equiv="content-type" content="text/html; charset=ISO-8859-1"> + <title>Detailed Design Template</title> +</head> + <body> + +<h1><font color="#cc0000">Gecko Layout Detailed Design Document</font></h1> + +<h1>Space Manager Detailed Design</h1> + +<h2>Overview</h2> +<p> + 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. +</p> + + + +<hr width="100%" size="2"> +<h2>nsSpaceManager</h2> +<p> + 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. +</p> + +<p> + 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. +</p> + +<p> + The class nsSpaceManager is declared in the file <a href="http://lxr.mozilla.org/seamonkey/source/layout/base/src/nsSpaceManager.h"> + nsSpaceManger.h</a> + . 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<font color="#cc0000"> + .</font> +</p> + +<p> + Here is the class declaration, taken from the source file as of 01.08.02 +</p> + + + +<pre>/** + * 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 +}; + +</pre> + +<h3>Public API</h3> + +<h4>Life Cycle:</h4> +<p> + 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. +</p> + +<pre> nsSpaceManager(nsIPresShell* aPresShell, nsIFrame* aFrame); + ~nsSpaceManager(); +</pre> +<p> + 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. +</p> + +<pre> + void* operator new(size_t aSize); + void operator delete(void* aPtr, size_t aSize); + +</pre> +<p> + 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. +</p> + +<pre> static void Shutdown(); + +</pre> + +<h4>Origin / Coordinate Space Translation</h4> + +<pre> /** + * 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; +</pre> + +<h4>Region Management</h4> + +<pre> /** + * 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(); +</pre> + +<h4>Float Impact</h4> + +<pre> /** + * 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); + } +</pre> + +<h4>Debug Only Methods</h4> + +<pre> /** + * Dump the state of the spacemanager out to a file + */ + nsresult List(FILE* out); + + void SizeOf(nsISizeOfHandler* aHandler, uint32_t* aResult) const; + +</pre> + +<h4>Unused / Obsolete Methods</h4> + +<pre> /* + * 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; } + +</pre> + +<h3>Implementation Notes</h3> + +<h4></h4> + +<h4>Algorithm 1: GetBandData</h4> +<p> +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. +</p> + +<p> +The algorithm to provide the band data is as follows: +</p> +<ul> + <li>Get a vertical offset in world coordinates (instead of frame-relative +coordinates) by adding the y-origin of the SpaceManager to the y offset passed +in</li> + <li>If the (adjusted) y value passed in is greater than the greatest band +being managed, then all space is available so a single trapezoid is returned, +marked as available and sized to the maximum size value (passed in).</li> + <li>If the (adjusted) y offset intersects a band, then gather the band +data:</li> + <ul> + <li>walk the internal bandData list from head to tail</li> + <li>for each band data entry, see if the top of the band is greater than +the (adjusted) y offset requested</li> + <li>if it is, then band is below the offset requested, so the area between +the band and the y offset is available - create a trapezoid with that region +and return it.</li> + <li>if the (adjusted) y offset is between the band top and bottom, then +get the available space for the band by calling GetBandAvailableSpace</li> + <li>otherwise, move to the next band</li> + </ul> +</ul> +<h5>GetBandAvailableSpace:</h5> +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. + +<ul> + <li>First, walk all of the bands until a band that is to the right of the +desired offset is located</li> + <li>Starting at that band, walk the remaining bands:</li> + <ul> + <li>if the current band is to the right of the requested band, then there +is available space. </li> + <ul> + <li>if there is more room in the bandData collection, then add a trapezoid +to the bandData collection such that it is marked as available and has a +rect that represents the space between the reference band tna dht band being +examined</li> + <li>if there is no more room in the BandData collection, estimate the +number of entries requires as the current count + twice the number of bands +below the reference band, plus two. Return an error code so the caller +can reallocate the collection and try again.</li> + </ul> + <li>check the size of the collection again, if there is no room left +then estimate the number of items requires as the current count + twice the +number of bands below the band in question plus one. </li> + <li>create a new trapezoid in the band collection that has a region corresponding +to the reference band rect, marked as occupied by either a single or multiple +frames.</li> + <li>move to the next band</li> + </ul> + <li>after walking all of the band data, se if we have reached the right +edge of the band. </li> + <ul> + <li>If not, then check for space in the band collection</li> + <ul> + <li>if there is no room left, then set the count to the current count +plus 1 and return an error.</li> + <li>otherwise, create another entry in the band collection, marked +as available, and with a rect corresponding to the area remainin in the band +(eg. from the right edge of the last band rect to the right edge of the band).</li> + </ul> + </ul> +</ul> + +<h4>Algorithm 2: AddRectRegion</h4> +Clients call into this method to notify the Space Manager that a new frame +is occupying some space. + +<ul> + <li>First, try to get frame info for the frame. If it is found, return +an error since the frame is already associated with a region in the Space +Manager.</li> + <li>Next, create a rect from the occupied space passed in by the caller, +transforming it first to world-coordinates by adding the Space Manager's +offset to the occupied space rect passed in.</li> + <li>Create a new Frame Info instance for the frame and rect, returning +an error if allocation fails.</li> + <li>Check if the occupied space rect (adjusted) is empty, if so, return +an error (<font color="#cc0000">NOTE: this could be done earlier, or +prevented by the caller</font>)</li> + <li>Allocate a new BandRect instance with the rect and frame as constructor +arguments, and insert it into the collection via InsertBandRect</li> +</ul> +<h5>InsertBandRect:</h5> +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: + +<pre>// 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 | +// +-----+ +// +</pre> +<ul> + <li>First, check for the easiest case, where there are no existing band +rects, or the band rect passed in is below the bottommost rect. In this case, +just append the band rect and return.</li> + <li>Starting at the head of the list of bandRects, check for intersection +with the rect passed in:</li> + <ul> + <li>case #1: the rect is totally above the current band rect, so insert +a new band rect before the current bandRect</li> + <li>cases #2 and #7: the rect is partially above the band rect, so it +is divided into two bandRects, one entirely above the band, and one containing +the remainder of the rect. Insert the part that is totally above the +bandRect before the current bandRect, as in case #1 above, and adjust the +other band rect to exclude the part already added.</li> + <li>case #5: the rect is totally below the current bandRect, so just +skip to the next band</li> + <li>case #3 and #4: rect is at least partially intersection with the +bandRect, so divide the current band into two parts, where the top part is +above the current rect. Move to the new band just created, which is +the next band.</li> + <li>case #6: the rect shares the bottom and height with the bandRect, +so just add the rect to the band.</li> + <li>case #4 and #7: create a new rect for the part that overlaps the +bandRect, and add it to the current bandRect (similar to case #6) and then +move on to the next band, removing that part from the rect passed in. If +no more bands, append the rect passed in to the end of the bandRect list.</li> + </ul> +</ul> +<i>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).</i> + + +<h4>Algorithm 3: RemoveRegion</h4> + When a float is removed, the Space Manager is notified by a call to RemoveRegion, +passing in the frame that is being removed. + +<ul> + <li>Get the FrameInfo for the frame passed in. If not found, an error is +returned.</li> + <li>If the rect for the frame is not empty, then visit each band in the +bandList:</li> + <ul> + <li>for each rect in the band: + + </li> + </ul> + <ul> + <ul> + <li>if the bandRect is occupied by the frame, either remove the frame +from the bandRect (if there are other frames sharing it) and remember that +it was shared</li> + <li>otherwise simply remove the bandRect (no other frames share it).</li> + <li>if the bandRect was shared, then try to coalesce adjacent bandRects</li> + <ul> + <li>if the previous bandRect is directly next to the current bandRect, +and they have the same frame list, then make the current bandRect cover the +previous bandRect's full region (adjust the left edge to be that of the previous +bandRect) and remove the previous bandRect.</li> + </ul> + </ul> + </ul> + <ul> + <li>if the current band or prior band had a rect occupied byu the frame, +then try to join the two bands via JoinBands</li> + </ul> + <li>Finally, destroy the frameInfo for the frame. + + </li> +</ul> + +<br> + +<hr width="100%" size="2"> +<h2>Cross-Component Algorithms</h2> + +<br> + + + +<hr width="100%" size="2"> +<h2>Tech Notes</h2> +<ul> + <li> + + </li> + +</ul> + + + + + +</body> +</html> |