michael@0: /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
michael@0: /* This Source Code Form is subject to the terms of the Mozilla Public
michael@0:  * License, v. 2.0. If a copy of the MPL was not distributed with this
michael@0:  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
michael@0: 
michael@0: /**
michael@0:  * A class which manages pending restyles.  This handles keeping track
michael@0:  * of what nodes restyles need to happen on and so forth.
michael@0:  */
michael@0: 
michael@0: #ifndef mozilla_RestyleTracker_h
michael@0: #define mozilla_RestyleTracker_h
michael@0: 
michael@0: #include "mozilla/dom/Element.h"
michael@0: #include "nsDataHashtable.h"
michael@0: #include "nsIFrame.h"
michael@0: #include "mozilla/SplayTree.h"
michael@0: 
michael@0: namespace mozilla {
michael@0: 
michael@0: class RestyleManager;
michael@0: 
michael@0: /** 
michael@0:  * Helper class that collects a list of frames that need
michael@0:  * UpdateOverflow() called on them, and coalesces them
michael@0:  * to avoid walking up the same ancestor tree multiple times.
michael@0:  */
michael@0: class OverflowChangedTracker
michael@0: {
michael@0: public:
michael@0:   enum ChangeKind {
michael@0:     /**
michael@0:      * The frame was explicitly added as a result of
michael@0:      * nsChangeHint_UpdatePostTransformOverflow and hence may have had a style
michael@0:      * change that changes its geometry relative to parent, without reflowing.
michael@0:      */
michael@0:     TRANSFORM_CHANGED,
michael@0:     /**
michael@0:      * The overflow areas of children have changed
michael@0:      * and we need to call UpdateOverflow on the frame.
michael@0:      */
michael@0:     CHILDREN_CHANGED,
michael@0:     /**
michael@0:      * The overflow areas of children have changed
michael@0:      * and we need to call UpdateOverflow on the frame.
michael@0:      * Also call UpdateOverflow on the parent even if the
michael@0:      * overflow areas of the frame does not change.
michael@0:      */
michael@0:     CHILDREN_AND_PARENT_CHANGED
michael@0:   };
michael@0: 
michael@0:   OverflowChangedTracker() :
michael@0:     mSubtreeRoot(nullptr)
michael@0:   {}
michael@0: 
michael@0:   ~OverflowChangedTracker()
michael@0:   {
michael@0:     NS_ASSERTION(mEntryList.empty(), "Need to flush before destroying!");
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Add a frame that has had a style change, and needs its
michael@0:    * overflow updated.
michael@0:    *
michael@0:    * If there are pre-transform overflow areas stored for this
michael@0:    * frame, then we will call FinishAndStoreOverflow with those
michael@0:    * areas instead of UpdateOverflow().
michael@0:    *
michael@0:    * If the overflow area changes, then UpdateOverflow will also
michael@0:    * be called on the parent.
michael@0:    */
michael@0:   void AddFrame(nsIFrame* aFrame, ChangeKind aChangeKind) {
michael@0:     uint32_t depth = aFrame->GetDepthInFrameTree();
michael@0:     Entry *entry = nullptr;
michael@0:     if (!mEntryList.empty()) {
michael@0:       entry = mEntryList.find(Entry(aFrame, depth));
michael@0:     }
michael@0:     if (entry == nullptr) {
michael@0:       // Add new entry.
michael@0:       mEntryList.insert(new Entry(aFrame, depth, aChangeKind));
michael@0:     } else {
michael@0:       // Update the existing entry if the new value is stronger.
michael@0:       entry->mChangeKind = std::max(entry->mChangeKind, aChangeKind);
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Remove a frame.
michael@0:    */
michael@0:   void RemoveFrame(nsIFrame* aFrame) {
michael@0:     if (mEntryList.empty()) {
michael@0:       return;
michael@0:     }
michael@0: 
michael@0:     uint32_t depth = aFrame->GetDepthInFrameTree();
michael@0:     if (mEntryList.find(Entry(aFrame, depth))) {
michael@0:       delete mEntryList.remove(Entry(aFrame, depth));
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Set the subtree root to limit overflow updates. This must be set if and
michael@0:    * only if currently reflowing aSubtreeRoot, to ensure overflow changes will
michael@0:    * still propagate correctly.
michael@0:    */
michael@0:   void SetSubtreeRoot(const nsIFrame* aSubtreeRoot) {
michael@0:     mSubtreeRoot = aSubtreeRoot;
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Update the overflow of all added frames, and clear the entry list.
michael@0:    *
michael@0:    * Start from those deepest in the frame tree and works upwards. This stops 
michael@0:    * us from processing the same frame twice.
michael@0:    */
michael@0:   void Flush() {
michael@0:     while (!mEntryList.empty()) {
michael@0:       Entry *entry = mEntryList.removeMin();
michael@0:       nsIFrame *frame = entry->mFrame;
michael@0: 
michael@0:       bool overflowChanged = false;
michael@0:       if (entry->mChangeKind == CHILDREN_AND_PARENT_CHANGED) {
michael@0:         // Need to union the overflow areas of the children.
michael@0:         // Always update the parent, even if the overflow does not change.
michael@0:         frame->UpdateOverflow();
michael@0:         overflowChanged = true;
michael@0:       } else if (entry->mChangeKind == CHILDREN_CHANGED) {
michael@0:         // Need to union the overflow areas of the children.
michael@0:         // Only update the parent if the overflow changes.
michael@0:         overflowChanged = frame->UpdateOverflow();
michael@0:       } else {
michael@0:         // Take a faster path that doesn't require unioning the overflow areas
michael@0:         // of our children.
michael@0: 
michael@0: #ifdef DEBUG
michael@0:         bool hasInitialOverflowPropertyApplied = false;
michael@0:         frame->Properties().Get(nsIFrame::DebugInitialOverflowPropertyApplied(),
michael@0:                                  &hasInitialOverflowPropertyApplied);
michael@0:         NS_ASSERTION(hasInitialOverflowPropertyApplied,
michael@0:                      "InitialOverflowProperty must be set first.");
michael@0: #endif
michael@0: 
michael@0:         nsOverflowAreas* overflow = 
michael@0:           static_cast<nsOverflowAreas*>(frame->Properties().Get(nsIFrame::InitialOverflowProperty()));
michael@0:         if (overflow) {
michael@0:           // FinishAndStoreOverflow will change the overflow areas passed in,
michael@0:           // so make a copy.
michael@0:           nsOverflowAreas overflowCopy = *overflow;
michael@0:           frame->FinishAndStoreOverflow(overflowCopy, frame->GetSize());
michael@0:         } else {
michael@0:           nsRect bounds(nsPoint(0, 0), frame->GetSize());
michael@0:           nsOverflowAreas boundsOverflow;
michael@0:           boundsOverflow.SetAllTo(bounds);
michael@0:           frame->FinishAndStoreOverflow(boundsOverflow, bounds.Size());
michael@0:         }
michael@0: 
michael@0:         // We can't tell if the overflow changed, so be conservative
michael@0:         overflowChanged = true;
michael@0:       }
michael@0: 
michael@0:       // If the frame style changed (e.g. positioning offsets)
michael@0:       // then we need to update the parent with the overflow areas of its
michael@0:       // children.
michael@0:       if (overflowChanged) {
michael@0:         nsIFrame *parent = frame->GetParent();
michael@0:         if (parent && parent != mSubtreeRoot) {
michael@0:           Entry* parentEntry = mEntryList.find(Entry(parent, entry->mDepth - 1));
michael@0:           if (parentEntry) {
michael@0:             parentEntry->mChangeKind = std::max(parentEntry->mChangeKind, CHILDREN_CHANGED);
michael@0:           } else {
michael@0:             mEntryList.insert(new Entry(parent, entry->mDepth - 1, CHILDREN_CHANGED));
michael@0:           }
michael@0:         }
michael@0:       }
michael@0:       delete entry;
michael@0:     }
michael@0:   }
michael@0:   
michael@0: private:
michael@0:   struct Entry : SplayTreeNode<Entry>
michael@0:   {
michael@0:     Entry(nsIFrame* aFrame, uint32_t aDepth, ChangeKind aChangeKind = CHILDREN_CHANGED)
michael@0:       : mFrame(aFrame)
michael@0:       , mDepth(aDepth)
michael@0:       , mChangeKind(aChangeKind)
michael@0:     {}
michael@0: 
michael@0:     bool operator==(const Entry& aOther) const
michael@0:     {
michael@0:       return mFrame == aOther.mFrame;
michael@0:     }
michael@0:  
michael@0:     /**
michael@0:      * Sort by *reverse* depth in the tree, and break ties with
michael@0:      * the frame pointer.
michael@0:      */
michael@0:     bool operator<(const Entry& aOther) const
michael@0:     {
michael@0:       if (mDepth == aOther.mDepth) {
michael@0:         return mFrame < aOther.mFrame;
michael@0:       }
michael@0:       return mDepth > aOther.mDepth; /* reverse, want "min" to be deepest */
michael@0:     }
michael@0: 
michael@0:     static int compare(const Entry& aOne, const Entry& aTwo)
michael@0:     {
michael@0:       if (aOne == aTwo) {
michael@0:         return 0;
michael@0:       } else if (aOne < aTwo) {
michael@0:         return -1;
michael@0:       } else {
michael@0:         return 1;
michael@0:       }
michael@0:     }
michael@0: 
michael@0:     nsIFrame* mFrame;
michael@0:     /* Depth in the frame tree */
michael@0:     uint32_t mDepth;
michael@0:     ChangeKind mChangeKind;
michael@0:   };
michael@0: 
michael@0:   /* A list of frames to process, sorted by their depth in the frame tree */
michael@0:   SplayTree<Entry, Entry> mEntryList;
michael@0: 
michael@0:   /* Don't update overflow of this frame or its ancestors. */
michael@0:   const nsIFrame* mSubtreeRoot;
michael@0: };
michael@0: 
michael@0: class RestyleTracker {
michael@0: public:
michael@0:   typedef mozilla::dom::Element Element;
michael@0: 
michael@0:   RestyleTracker(uint32_t aRestyleBits) :
michael@0:     mRestyleBits(aRestyleBits),
michael@0:     mHaveLaterSiblingRestyles(false)
michael@0:   {
michael@0:     NS_PRECONDITION((mRestyleBits & ~ELEMENT_ALL_RESTYLE_FLAGS) == 0,
michael@0:                     "Why do we have these bits set?");
michael@0:     NS_PRECONDITION((mRestyleBits & ELEMENT_PENDING_RESTYLE_FLAGS) != 0,
michael@0:                     "Must have a restyle flag");
michael@0:     NS_PRECONDITION((mRestyleBits & ELEMENT_PENDING_RESTYLE_FLAGS) !=
michael@0:                       ELEMENT_PENDING_RESTYLE_FLAGS,
michael@0:                     "Shouldn't have both restyle flags set");
michael@0:     NS_PRECONDITION((mRestyleBits & ~ELEMENT_PENDING_RESTYLE_FLAGS) != 0,
michael@0:                     "Must have root flag");
michael@0:     NS_PRECONDITION((mRestyleBits & ~ELEMENT_PENDING_RESTYLE_FLAGS) !=
michael@0:                     (ELEMENT_ALL_RESTYLE_FLAGS & ~ELEMENT_PENDING_RESTYLE_FLAGS),
michael@0:                     "Shouldn't have both root flags");
michael@0:   }
michael@0: 
michael@0:   void Init(RestyleManager* aRestyleManager) {
michael@0:     mRestyleManager = aRestyleManager;
michael@0:   }
michael@0: 
michael@0:   uint32_t Count() const {
michael@0:     return mPendingRestyles.Count();
michael@0:   }
michael@0: 
michael@0:   /**
michael@0:    * Add a restyle for the given element to the tracker.  Returns true
michael@0:    * if the element already had eRestyle_LaterSiblings set on it.
michael@0:    */
michael@0:   bool AddPendingRestyle(Element* aElement, nsRestyleHint aRestyleHint,
michael@0:                            nsChangeHint aMinChangeHint);
michael@0: 
michael@0:   /**
michael@0:    * Process the restyles we've been tracking.
michael@0:    */
michael@0:   void ProcessRestyles() {
michael@0:     // Fast-path the common case (esp. for the animation restyle
michael@0:     // tracker) of not having anything to do.
michael@0:     if (mPendingRestyles.Count()) {
michael@0:       DoProcessRestyles();
michael@0:     }
michael@0:   }
michael@0: 
michael@0:   // Return our ELEMENT_HAS_PENDING_(ANIMATION_)RESTYLE bit
michael@0:   uint32_t RestyleBit() const {
michael@0:     return mRestyleBits & ELEMENT_PENDING_RESTYLE_FLAGS;
michael@0:   }
michael@0: 
michael@0:   // Return our ELEMENT_IS_POTENTIAL_(ANIMATION_)RESTYLE_ROOT bit
michael@0:   uint32_t RootBit() const {
michael@0:     return mRestyleBits & ~ELEMENT_PENDING_RESTYLE_FLAGS;
michael@0:   }
michael@0:   
michael@0:   struct RestyleData {
michael@0:     nsRestyleHint mRestyleHint;  // What we want to restyle
michael@0:     nsChangeHint  mChangeHint;   // The minimal change hint for "self"
michael@0:   };
michael@0: 
michael@0:   /**
michael@0:    * If the given Element has a restyle pending for it, return the
michael@0:    * relevant restyle data.  This function will clear everything other
michael@0:    * than a possible eRestyle_LaterSiblings hint for aElement out of
michael@0:    * our hashtable.  The returned aData will never have an
michael@0:    * eRestyle_LaterSiblings hint in it.
michael@0:    *
michael@0:    * The return value indicates whether any restyle data was found for
michael@0:    * the element.  If false is returned, then the state of *aData is
michael@0:    * undefined.
michael@0:    */
michael@0:   bool GetRestyleData(Element* aElement, RestyleData* aData);
michael@0: 
michael@0:   /**
michael@0:    * The document we're associated with.
michael@0:    */
michael@0:   inline nsIDocument* Document() const;
michael@0: 
michael@0:   struct RestyleEnumerateData : public RestyleData {
michael@0:     nsRefPtr<Element> mElement;
michael@0:   };
michael@0: 
michael@0: private:
michael@0:   /**
michael@0:    * Handle a single mPendingRestyles entry.  aRestyleHint must not
michael@0:    * include eRestyle_LaterSiblings; that needs to be dealt with
michael@0:    * before calling this function.
michael@0:    */
michael@0:   inline void ProcessOneRestyle(Element* aElement,
michael@0:                                 nsRestyleHint aRestyleHint,
michael@0:                                 nsChangeHint aChangeHint);
michael@0: 
michael@0:   /**
michael@0:    * The guts of our restyle processing.
michael@0:    */
michael@0:   void DoProcessRestyles();
michael@0: 
michael@0:   typedef nsDataHashtable<nsISupportsHashKey, RestyleData> PendingRestyleTable;
michael@0:   typedef nsAutoTArray< nsRefPtr<Element>, 32> RestyleRootArray;
michael@0:   // Our restyle bits.  These will be a subset of ELEMENT_ALL_RESTYLE_FLAGS, and
michael@0:   // will include one flag from ELEMENT_PENDING_RESTYLE_FLAGS and one flag
michael@0:   // that's not in ELEMENT_PENDING_RESTYLE_FLAGS.
michael@0:   uint32_t mRestyleBits;
michael@0:   RestyleManager* mRestyleManager; // Owns us
michael@0:   // A hashtable that maps elements to RestyleData structs.  The
michael@0:   // values only make sense if the element's current document is our
michael@0:   // document and it has our RestyleBit() flag set.  In particular,
michael@0:   // said bit might not be set if the element had a restyle posted and
michael@0:   // then was moved around in the DOM.
michael@0:   PendingRestyleTable mPendingRestyles;
michael@0:   // An array that keeps track of our possible restyle roots.  This
michael@0:   // maintains the invariant that if A and B are both restyle roots
michael@0:   // and A is an ancestor of B then A will come after B in the array.
michael@0:   // We maintain this invariant by checking whether an element has an
michael@0:   // ancestor with the restyle root bit set before appending it to the
michael@0:   // array.
michael@0:   RestyleRootArray mRestyleRoots;
michael@0:   // True if we have some entries with the eRestyle_LaterSiblings
michael@0:   // flag.  We need this to avoid enumerating the hashtable looking
michael@0:   // for such entries when we can't possibly have any.
michael@0:   bool mHaveLaterSiblingRestyles;
michael@0: };
michael@0: 
michael@0: inline bool RestyleTracker::AddPendingRestyle(Element* aElement,
michael@0:                                                 nsRestyleHint aRestyleHint,
michael@0:                                                 nsChangeHint aMinChangeHint)
michael@0: {
michael@0:   RestyleData existingData;
michael@0:   existingData.mRestyleHint = nsRestyleHint(0);
michael@0:   existingData.mChangeHint = NS_STYLE_HINT_NONE;
michael@0: 
michael@0:   // Check the RestyleBit() flag before doing the hashtable Get, since
michael@0:   // it's possible that the data in the hashtable isn't actually
michael@0:   // relevant anymore (if the flag is not set).
michael@0:   if (aElement->HasFlag(RestyleBit())) {
michael@0:     mPendingRestyles.Get(aElement, &existingData);
michael@0:   } else {
michael@0:     aElement->SetFlags(RestyleBit());
michael@0:   }
michael@0: 
michael@0:   bool hadRestyleLaterSiblings =
michael@0:     (existingData.mRestyleHint & eRestyle_LaterSiblings) != 0;
michael@0:   existingData.mRestyleHint =
michael@0:     nsRestyleHint(existingData.mRestyleHint | aRestyleHint);
michael@0:   NS_UpdateHint(existingData.mChangeHint, aMinChangeHint);
michael@0: 
michael@0:   mPendingRestyles.Put(aElement, existingData);
michael@0: 
michael@0:   // We can only treat this element as a restyle root if we would
michael@0:   // actually restyle its descendants (so either call
michael@0:   // ReResolveStyleContext on it or just reframe it).
michael@0:   if ((aRestyleHint & (eRestyle_Self | eRestyle_Subtree)) ||
michael@0:       (aMinChangeHint & nsChangeHint_ReconstructFrame)) {
michael@0:     for (const Element* cur = aElement; !cur->HasFlag(RootBit()); ) {
michael@0:       nsIContent* parent = cur->GetFlattenedTreeParent();
michael@0:       // Stop if we have no parent or the parent is not an element or
michael@0:       // we're part of the viewport scrollbars (because those are not
michael@0:       // frametree descendants of the primary frame of the root
michael@0:       // element).
michael@0:       // XXXbz maybe the primary frame of the root should be the root scrollframe?
michael@0:       if (!parent || !parent->IsElement() ||
michael@0:           // If we've hit the root via a native anonymous kid and that
michael@0:           // this native anonymous kid is not obviously a descendant
michael@0:           // of the root's primary frame, assume we're under the root
michael@0:           // scrollbars.  Since those don't get reresolved when
michael@0:           // reresolving the root, we need to make sure to add the
michael@0:           // element to mRestyleRoots.
michael@0:           (cur->IsInNativeAnonymousSubtree() && !parent->GetParent() &&
michael@0:            cur->GetPrimaryFrame() &&
michael@0:            cur->GetPrimaryFrame()->GetParent() != parent->GetPrimaryFrame())) {
michael@0:         mRestyleRoots.AppendElement(aElement);
michael@0:         break;
michael@0:       }
michael@0:       cur = parent->AsElement();
michael@0:     }
michael@0:     // At this point some ancestor of aElement (possibly aElement
michael@0:     // itself) is in mRestyleRoots.  Set the root bit on aElement, to
michael@0:     // speed up searching for an existing root on its descendants.
michael@0:     aElement->SetFlags(RootBit());
michael@0:   }
michael@0: 
michael@0:   mHaveLaterSiblingRestyles =
michael@0:     mHaveLaterSiblingRestyles || (aRestyleHint & eRestyle_LaterSiblings) != 0;
michael@0:   return hadRestyleLaterSiblings;
michael@0: }
michael@0: 
michael@0: } // namespace mozilla
michael@0: 
michael@0: #endif /* mozilla_RestyleTracker_h */