layout/generic/CSSOrderAwareFrameIterator.h
author Nika Layzell <nika@thelayzells.com>
Tue, 25 Sep 2018 17:34:53 +0200
changeset 507828 5e6dae0c1e5a4939ccd406f14607f7fafffd45a7
parent 438505 821e6c2ceda2658ff2a22e1ebc027bb309d514b4
child 508163 6f3709b3878117466168c40affa7bca0b60cf75b
permissions -rw-r--r--
Bug 1448426 - Wrap windows.h to avoid problematic define statements, r=froydnj,glandium By default, windows.h exposes a large number of problematic define statements which are UpperCamelCase, such as a define from `CreateWindow` to `CreateWindow{A,W}`. As many of these names are generic (e.g. CreateFile, CreateWindow), they can mess up Gecko code that may legitimately have its own methods with the same names. The header also defines some traditional SCREAMING_SNAKE_CASE defines which can mess up our code by conflicting with local values. This patch adds a simple code generator which generates wrappers for these defines, and uses them to wrap the windows.h wrapper using the `stl_wrappers` mechanism, allowing us to use windows.h in more places. Differential Revision: https://phabricator.services.mozilla.com/D10932

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* 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/. */

/* Iterator class for frame lists that respect CSS "order" during layout */

#ifndef mozilla_CSSOrderAwareFrameIterator_h
#define mozilla_CSSOrderAwareFrameIterator_h

#include <algorithm>
#include "nsFrameList.h"
#include "nsIFrame.h"
#include "mozilla/Maybe.h"
#include "mozilla/Assertions.h"

#if defined(__clang__) && __clang_major__ == 3 && __clang_minor__ <= 9
#define CLANG_CRASH_BUG 1
#endif

namespace mozilla {

/**
 * CSSOrderAwareFrameIteratorT is a base class for iterators that traverse
 * child frame lists in a way that respects their CSS "order" property.
 *   https://drafts.csswg.org/css-flexbox-1/#order-property
 * This class isn't meant to be directly used; instead, use its specializations
 * CSSOrderAwareFrameIterator and ReverseCSSOrderAwareFrameIterator.
 *
 * Client code can use a CSSOrderAwareFrameIterator to traverse lower-"order"
 * frames before higher-"order" ones (as required for correct flex/grid
 * layout), without modifying the frames' actual ordering within the frame
 * tree. Any frames with equal "order" values will be traversed consecutively,
 * in frametree order (which is generally equivalent to DOM order).
 *
 * By default, the iterator will skip past placeholder frames during
 * iteration. You can adjust this behavior via the ChildFilter constructor arg.
 *
 * By default, the iterator will use the frames' CSS "order" property to
 * determine its traversal order. However, it can be customized to instead use
 * the (prefixed) legacy "box-ordinal-group" CSS property instead, as part of
 * emulating "display:-webkit-box" containers. This behavior can be customized
 * using the OrderingProperty constructor arg.
 *
 * A few notes on performance:
 *  - If you're iterating multiple times in a row, it's a good idea to reuse
 * the same iterator (calling Reset() to start each new iteration), rather than
 * instantiating a new one each time.
 *  - If you have foreknowledge of the list's orderedness, you can save some
 * time by passing eKnownOrdered or eKnownUnordered to the constructor (which
 * will skip some checks during construction).
 *
 * Warning: if the given frame list changes, it makes the iterator invalid and
 * bad things will happen if it's used further.
 */
template<typename Iterator>
class CSSOrderAwareFrameIteratorT
{
public:
  enum OrderState { eUnknownOrder, eKnownOrdered, eKnownUnordered };
  enum ChildFilter { eSkipPlaceholders, eIncludeAll };
  enum OrderingProperty {
    eUseOrder,          // Default behavior: use "order".
    eUseBoxOrdinalGroup // Legacy behavior: use prefixed "box-ordinal-group".
  };
  CSSOrderAwareFrameIteratorT(nsIFrame* aContainer,
                              nsIFrame::ChildListID aListID,
                              ChildFilter aFilter = eSkipPlaceholders,
                              OrderState aState = eUnknownOrder,
                              OrderingProperty aOrderProp = eUseOrder)
    : mChildren(aContainer->GetChildList(aListID))
    , mArrayIndex(0)
    , mItemIndex(0)
    , mSkipPlaceholders(aFilter == eSkipPlaceholders)
#ifdef DEBUG
    , mContainer(aContainer)
    , mListID(aListID)
#endif
  {
    MOZ_ASSERT(aContainer->IsFlexOrGridContainer(),
               "Only use this iterator in a container that honors 'order'");

    size_t count = 0;
    bool isOrdered = aState != eKnownUnordered;
    if (aState == eUnknownOrder) {
      auto maxOrder = std::numeric_limits<int32_t>::min();
      for (auto child : mChildren) {
        ++count;

        int32_t order;
        if (aOrderProp == eUseBoxOrdinalGroup) {
          // We'll be using mBoxOrdinal, which has type uint32_t. However, the
          // modern 'order' property (whose functionality we're co-opting) has
          // type int32_t.  So: if we happen to have a uint32_t value that's
          // greater than INT32_MAX, we clamp it rather than letting it
          // overflow. Chances are, this is just an author using BIG_VALUE
          // anyway, so the clamped value should be fine.
          uint32_t clampedBoxOrdinal =
            std::min(child->StyleXUL()->mBoxOrdinal,
                     static_cast<uint32_t>(INT32_MAX));
          order = static_cast<int32_t>(clampedBoxOrdinal);
        } else {
          order = child->StylePosition()->mOrder;
        }

        if (order < maxOrder) {
          isOrdered = false;
          break;
        }
        maxOrder = order;
      }
    }
    if (isOrdered) {
      mIter.emplace(begin(mChildren));
      mIterEnd.emplace(end(mChildren));
    } else {
      count *= 2; // XXX somewhat arbitrary estimate for now...
      mArray.emplace(count);
      for (Iterator i(begin(mChildren)), iEnd(end(mChildren)); i != iEnd; ++i) {
        mArray->AppendElement(*i);
      }
      auto comparator = (aOrderProp == eUseBoxOrdinalGroup)
        ? CSSBoxOrdinalGroupComparator
        : CSSOrderComparator;

      // XXX replace this with nsTArray::StableSort when bug 1147091 is fixed.
      std::stable_sort(mArray->begin(), mArray->end(), comparator);
    }

    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }
  ~CSSOrderAwareFrameIteratorT()
  {
    MOZ_ASSERT(IsForward() == mItemCount.isNothing());
  }

  bool IsForward() const;
  Iterator begin(const nsFrameList& aList);
  Iterator end(const nsFrameList& aList);

  nsIFrame* operator*() const
  {
    MOZ_ASSERT(!AtEnd());
    if (mIter.isSome()) {
      return **mIter;
    }
    return (*mArray)[mArrayIndex];
  }

  /**
   * Return the child index of the current item, placeholders not counted.
   * It's forbidden to call this method when the current frame is placeholder.
   */
  size_t ItemIndex() const
  {
    MOZ_ASSERT(!AtEnd());
    MOZ_ASSERT(!(**this)->IsPlaceholderFrame(),
               "MUST not call this when at a placeholder");
    MOZ_ASSERT(IsForward() || mItemIndex < *mItemCount,
               "Returning an out-of-range mItemIndex...");
    return mItemIndex;
  }

  void SetItemCount(size_t aItemCount)
  {
#ifndef CLANG_CRASH_BUG
    MOZ_ASSERT(mIter.isSome() || aItemCount <= mArray->Length(),
               "item count mismatch");
#endif
    mItemCount.emplace(aItemCount);
    // Note: it's OK if mItemIndex underflows -- ItemIndex()
    // will not be called unless there is at least one item.
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
  }

  /**
   * Skip over placeholder children.
   */
  void SkipPlaceholders()
  {
    if (mIter.isSome()) {
      for (; *mIter != *mIterEnd; ++*mIter) {
        nsIFrame* child = **mIter;
        if (!child->IsPlaceholderFrame()) {
          return;
        }
      }
    } else {
      for (; mArrayIndex < mArray->Length(); ++mArrayIndex) {
        nsIFrame* child = (*mArray)[mArrayIndex];
        if (!child->IsPlaceholderFrame()) {
          return;
        }
      }
    }
  }

  bool AtEnd() const
  {
#ifndef CLANG_CRASH_BUG
    // Clang 3.6.2 crashes when compiling this assertion:
    MOZ_ASSERT(mIter.isSome() || mArrayIndex <= mArray->Length());
#endif
    return mIter ? (*mIter == *mIterEnd) : mArrayIndex >= mArray->Length();
  }

  void Next()
  {
#ifdef DEBUG
    MOZ_ASSERT(!AtEnd());
    nsFrameList list = mContainer->GetChildList(mListID);
    MOZ_ASSERT(list.FirstChild() == mChildren.FirstChild() &&
               list.LastChild() == mChildren.LastChild(),
               "the list of child frames must not change while iterating!");
#endif
    if (mSkipPlaceholders || !(**this)->IsPlaceholderFrame()) {
      IsForward() ? ++mItemIndex : --mItemIndex;
    }
    if (mIter.isSome()) {
      ++*mIter;
    } else {
      ++mArrayIndex;
    }
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  void Reset(ChildFilter aFilter = eSkipPlaceholders)
  {
    if (mIter.isSome()) {
      mIter.reset();
      mIter.emplace(begin(mChildren));
      mIterEnd.reset();
      mIterEnd.emplace(end(mChildren));
    } else {
      mArrayIndex = 0;
    }
    mItemIndex = IsForward() ? 0 : *mItemCount - 1;
    mSkipPlaceholders = aFilter == eSkipPlaceholders;
    if (mSkipPlaceholders) {
      SkipPlaceholders();
    }
  }

  bool IsValid() const { return mIter.isSome() || mArray.isSome(); }

  void Invalidate()
  {
    mIter.reset();
    mArray.reset();
    mozWritePoison(&mChildren, sizeof(mChildren));
  }

  bool ItemsAreAlreadyInOrder() const { return mIter.isSome(); }

  static bool CSSOrderComparator(nsIFrame* const& a, nsIFrame* const& b);
  static bool CSSBoxOrdinalGroupComparator(nsIFrame* const& a, nsIFrame* const& b);
private:
  nsFrameList mChildren;
  // Used if child list is already in ascending 'order'.
  Maybe<Iterator> mIter;
  Maybe<Iterator> mIterEnd;
  // Used if child list is *not* in ascending 'order'.
  // This array is pre-sorted in reverse order for a reverse iterator.
  Maybe<nsTArray<nsIFrame*>> mArray;
  size_t mArrayIndex;
  // The index of the current item (placeholders excluded).
  size_t mItemIndex;
  // The number of items (placeholders excluded).
  // It's only initialized and used in a reverse iterator.
  Maybe<size_t> mItemCount;
  // Skip placeholder children in the iteration?
  bool mSkipPlaceholders;
#ifdef DEBUG
  nsIFrame* mContainer;
  nsIFrame::ChildListID mListID;
#endif
};

typedef CSSOrderAwareFrameIteratorT<nsFrameList::iterator>
  CSSOrderAwareFrameIterator;
typedef CSSOrderAwareFrameIteratorT<nsFrameList::reverse_iterator>
  ReverseCSSOrderAwareFrameIterator;

} // namespace mozilla

#endif // mozilla_CSSOrderAwareFrameIterator_h