Quelle  nsRegion.h   Sprache: C

/* -*- 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/. */

#ifndef nsRegion_h__
#define nsRegion_h__

#include <stddef.h>  // for size_t
#include <stdint.h>  // for uint32_t, uint64_t

#include <ostream>  // for std::ostream
#include <utility>  // for mozilla::Move

#include "mozilla/ArrayView.h"      // for ArrayView
#include "mozilla/gfx/MatrixFwd.h"  // for mozilla::gfx::Matrix4x4
#include "nsCoord.h"                // for nscoord
#include "nsMargin.h"               // for nsIntMargin
#include "nsPoint.h"                // for nsIntPoint, nsPoint
#include "nsRect.h"                 // for mozilla::gfx::IntRect, nsRect
#include "nsRectAbsolute.h"
#include "nsRegionFwd.h"  // for nsIntRegion
#include "nsString.h"     // for nsCString
#include "nsTArray.h"
#include "pixman.h"

// Uncomment this line to get additional integrity checking.
// #define DEBUG_REGIONS
#ifdef DEBUG_REGIONS
#  include <sstream>
#endif

/* For information on the internal representation look at pixman-region.c
 *
 * This replaces an older homebrew implementation of nsRegion. The
 * representation used here may use more rectangles than nsRegion however, the
 * representation is canonical.  This means that there's no need for an
 * Optimize() method because for a paticular region there is only one
 * representation. This means that nsIntRegion will have more predictable
 * performance characteristics than the old nsRegion and should not become
 * degenerate.
 *
 * The pixman region code originates from X11 which has spread to a variety of
 * projects including Qt, Gtk, Wine. It should perform reasonably well.
 */

enum class VisitSide { TOP, BOTTOM, LEFT, RIGHT };

namespace regiondetails {
struct Band;
}

template <>
struct nsTArray_RelocationStrategy<regiondetails::Band> {
  typedef nsTArray_RelocateUsingMoveConstructor<regiondetails::Band> Type;
};

namespace regiondetails {

template <typename T, typename E>
class UncheckedArray : public T {
 public:
  using T::Elements;
  using T::Length;

  UncheckedArray() = default;
  MOZ_IMPLICIT UncheckedArray(T&& aSrc) : T(std::move(aSrc)) {}

  E& operator[](size_t aIndex) { return Elements()[aIndex]; }
  const E& operator[](size_t aIndex) const { return Elements()[aIndex]; }
  E& LastElement() { return Elements()[Length() - 1]; }
  const E& LastElement() const { return Elements()[Length() - 1]; }

  using iterator = E*;
  using const_iterator = const E*;

  iterator begin() { return iterator(Elements()); }
  const_iterator begin() const { return const_iterator(Elements()); }
  const_iterator cbegin() const { return begin(); }
  iterator end() { return iterator(Elements() + Length()); }
  const_iterator end() const { return const_iterator(Elements() + Length()); }
  const_iterator cend() const { return end(); }
};

struct Strip {
  // Default constructor should never be called, but is required for
  // vector::resize to compile.
  Strip() { MOZ_CRASH(); }
  Strip(int32_t aLeft, int32_t aRight) : left(aLeft), right(aRight) {}

  bool operator!=(const Strip& aOther) const {
    return left != aOther.left || right != aOther.right;
  }

  uint32_t Size() const { return right - left; }

  int32_t left;
  int32_t right;
};

struct Band {
  using Strip = regiondetails::Strip;
#ifndef DEBUG
  using StripArray =
      regiondetails::UncheckedArray<CopyableAutoTArray<Strip, 2>, Strip>;
#else
  using StripArray = CopyableAutoTArray<Strip, 2>;
#endif

  MOZ_IMPLICIT Band(const nsRectAbsolute& aRect)
      : top(aRect.Y()), bottom(aRect.YMost()) {
    mStrips.AppendElement(Strip{aRect.X(), aRect.XMost()});
  }

  Band(const Band& aOther) = default;
  Band(Band&& aOther) = default;

  void InsertStrip(const Strip& aStrip) {
    for (size_t i = 0; i < mStrips.Length(); i++) {
      Strip& strip = mStrips[i];
      if (strip.left > aStrip.right) {
        // Current strip is beyond aStrip, insert aStrip before.
        mStrips.InsertElementAt(i, aStrip);
        return;
      }

      if (strip.right < aStrip.left) {
        // Current strip is before aStrip, try the next.
        continue;
      }

      // Current strip intersects with aStrip, extend to the lext.
      strip.left = std::min(strip.left, aStrip.left);

      if (strip.right >= aStrip.right) {
        // Current strip extends beyond aStrip, done.
        return;
      }

      size_t next = i;
      next++;
      // Consume any subsequent strips intersecting with aStrip.
      while (next < mStrips.Length() && mStrips[next].left <= aStrip.right) {
        strip.right = mStrips[next].right;

        mStrips.RemoveElementAt(next);
      }

      // Extend the strip in case the aStrip goes on beyond it.
      strip.right = std::max(strip.right, aStrip.right);
      return;
    }
    mStrips.AppendElement(aStrip);
  }

  void SubStrip(const Strip& aStrip) {
    for (size_t i = 0; i < mStrips.Length(); i++) {
      Strip& strip = mStrips[i];
      if (strip.left > aStrip.right) {
        // Strip is entirely to the right of aStrip. Done.
        return;
      }

      if (strip.right < aStrip.left) {
        // Strip is entirely to the left of aStrip. Move on.
        continue;
      }

      if (strip.left < aStrip.left) {
        if (strip.right <= aStrip.right) {
          strip.right = aStrip.left;
          // This strip lies to the left of the start of aStrip.
          continue;
        }

        // aStrip is completely contained by this strip.
        Strip newStrip(aStrip.right, strip.right);
        strip.right = aStrip.left;
        if (i < mStrips.Length()) {
          i++;
          mStrips.InsertElementAt(i, newStrip);
        } else {
          mStrips.AppendElement(newStrip);
        }
        return;
      }

      // This strip lies to the right of the start of aStrip.
      if (strip.right <= aStrip.right) {
        // aStrip completely contains this strip.
        mStrips.RemoveElementAt(i);
        // Make sure we evaluate the strip now at i. This loop will increment.
        i--;
        continue;
      }
      strip.left = aStrip.right;
      return;
    }
  }

  bool Intersects(const Strip& aStrip) const {
    for (const Strip& strip : mStrips) {
      if (strip.left >= aStrip.right) {
        return false;
      }

      if (strip.right <= aStrip.left) {
        continue;
      }

      return true;
    }
    return false;
  }

  bool IntersectStripBounds(Strip& aStrip) const {
    bool intersected = false;

    int32_t rightMost;
    for (const Strip& strip : mStrips) {
      if (strip.left > aStrip.right) {
        break;
      }

      if (strip.right <= aStrip.left) {
        continue;
      }

      if (!intersected) {
        // First intersection, this is where the left side begins.
        aStrip.left = std::max(aStrip.left, strip.left);
      }

      intersected = true;
      // Expand to the right for each intersecting strip found.
      rightMost = std::min(strip.right, aStrip.right);
    }

    if (intersected) {
      aStrip.right = rightMost;
    } else {
      aStrip.right = aStrip.left = 0;
    }
    return intersected;
  }

  bool ContainsStrip(const Strip& aStrip) const {
    for (const Strip& strip : mStrips) {
      if (strip.left > aStrip.left) {
        return false;
      }

      if (strip.right >= aStrip.right) {
        return true;
      }
    }
    return false;
  }

  bool EqualStrips(const Band& aBand) const {
    if (mStrips.Length() != aBand.mStrips.Length()) {
      return false;
    }

    for (auto iter1 = mStrips.begin(), iter2 = aBand.mStrips.begin();
         iter1 != mStrips.end(); iter1++, iter2++) {
      if (*iter1 != *iter2) {
        return false;
      }
    }

    return true;
  }

  void IntersectStrip(const Strip& aStrip) {
    size_t i = 0;

    while (i < mStrips.Length()) {
      Strip& strip = mStrips[i];
      if (strip.right <= aStrip.left) {
        mStrips.RemoveElementAt(i);
        continue;
      }

      if (strip.left >= aStrip.right) {
        mStrips.TruncateLength(i);
        return;
      }

      strip.left = std::max(aStrip.left, strip.left);
      strip.right = std::min(aStrip.right, strip.right);
      i++;
    }
  }

  void IntersectStrips(const Band& aOther) {
    auto iter = mStrips.begin();
    auto iterOther = aOther.mStrips.begin();

    StripArray newStrips;

    // This function finds the intersection between two sets of strips.
    while (true) {
      while (true) {
        while (iter != mStrips.end() && iter->right <= iterOther->left) {
          // Increment our current strip until it ends beyond aOther's current
          // strip.
          iter++;
        }

        if (iter == mStrips.end()) {
          // End of our strips. Done.
          break;
        }

        while (iterOther != aOther.mStrips.end() &&
               iterOther->right <= iter->left) {
          // Increment aOther's current strip until it lies beyond our current
          // strip.
          iterOther++;
        }

        if (iterOther == aOther.mStrips.end()) {
          // End of aOther's strips. Done.
          break;
        }

        if (iterOther->left < iter->right) {
          // Intersection!
          break;
        }
      }

      if (iter == mStrips.end() || iterOther == aOther.mStrips.end()) {
        break;
      }

      newStrips.AppendElement(Strip(std::max(iter->left, iterOther->left),
                                    std::min(iterOther->right, iter->right)));

      if (iterOther->right < iter->right) {
        iterOther++;
        if (iterOther == aOther.mStrips.end()) {
          break;
        }
      } else {
        iter++;
      }
    }

    mStrips = std::move(newStrips);
  }

  bool Intersects(const Band& aOther) const {
    auto iter = mStrips.begin();
    auto iterOther = aOther.mStrips.begin();

    // This function finds the intersection between two sets of strips.
    while (true) {
      while (true) {
        while (iter != mStrips.end() && iter->right <= iterOther->left) {
          // Increment our current strip until it ends beyond aOther's current
          // strip.
          iter++;
        }

        if (iter == mStrips.end()) {
          // End of our strips. Done.
          break;
        }

        while (iterOther != aOther.mStrips.end() &&
               iterOther->right <= iter->left) {
          // Increment aOther's current strip until it lies beyond our current
          // strip.
          iterOther++;
        }

        if (iterOther == aOther.mStrips.end()) {
          // End of aOther's strips. Done.
          break;
        }

        if (iterOther->left < iter->right) {
          // Intersection!
          break;
        }
      }

      if (iter == mStrips.end() || iterOther == aOther.mStrips.end()) {
        break;
      }

      return true;
    }
    return false;
  }

  void SubStrips(const Band& aOther) {
    size_t idx = 0;
    auto iterOther = aOther.mStrips.begin();

    // This function finds the intersection between two sets of strips.
    while (true) {
      while (true) {
        while (idx < mStrips.Length() &&
               mStrips[idx].right <= iterOther->left) {
          // Increment our current strip until it ends beyond aOther's current
          // strip.
          idx++;
        }

        if (idx == mStrips.Length()) {
          // End of our strips. Done.
          break;
        }

        while (iterOther != aOther.mStrips.end() &&
               iterOther->right <= mStrips[idx].left) {
          // Increment aOther's current strip until it lies beyond our current
          // strip.
          iterOther++;
        }

        if (iterOther == aOther.mStrips.end()) {
          // End of aOther's strips. Done.
          break;
        }

        if (iterOther->left < mStrips[idx].right) {
          // Intersection!
          break;
        }
      }

      if (idx == mStrips.Length() || iterOther == aOther.mStrips.end()) {
        break;
      }

      if (mStrips[idx].left < iterOther->left) {
        size_t oldIdx = idx;
        // Our strip starts beyond other's
        if (mStrips[idx].right > iterOther->right) {
          // Our strip ends beyond other's as well.
          Strip newStrip(mStrips[idx]);
          newStrip.left = iterOther->right;
          mStrips.InsertElementAt(idx + 1, newStrip);
          idx++;
        }
        mStrips[oldIdx].right = iterOther->left;
        // Either idx was just incremented, or the current index no longer
        // intersects with iterOther.
        continue;
      } else if (mStrips[idx].right > iterOther->right) {
        mStrips[idx].left = iterOther->right;
        // Current strip no longer intersects, continue.
        iterOther++;
        if (iterOther == aOther.mStrips.end()) {
          break;
        }
        continue;
      }

      // Our current strip is completely contained by the other strip.
      mStrips.RemoveElementAt(idx);
    }
  }

  int32_t top;
  int32_t bottom;
  StripArray mStrips;
};
}  // namespace regiondetails

class nsRegion {
 public:
  using Band = regiondetails::Band;
  using Strip = regiondetails::Strip;
#ifndef DEBUG
  using BandArray = regiondetails::UncheckedArray<nsTArray<Band>, Band>;
  using StripArray = regiondetails::UncheckedArray<AutoTArray<Strip, 2>, Strip>;
#else
  using BandArray = nsTArray<Band>;
  using StripArray = AutoTArray<Strip, 2>;
#endif

  typedef nsRect RectType;
  typedef nsPoint PointType;
  typedef nsMargin MarginType;

  nsRegion() = default;
  MOZ_IMPLICIT nsRegion(const nsRect& aRect) {
    mBounds = nsRectAbsolute::FromRect(aRect);
  }
  MOZ_IMPLICIT nsRegion(const nsRectAbsolute& aRect) { mBounds = aRect; }
  explicit nsRegion(mozilla::gfx::ArrayView<pixman_box32_t> aRects) {
    for (uint32_t i = 0; i < aRects.Length(); i++) {
      AddRect(BoxToRect(aRects[i]));
    }
  }

  nsRegion(const nsRegion& aRegion) { Copy(aRegion); }
  nsRegion(nsRegion&& aRegion)
      : mBands(std::move(aRegion.mBands)), mBounds(aRegion.mBounds) {
    aRegion.SetEmpty();
  }
  nsRegion& operator=(nsRegion&& aRegion) {
    mBands = std::move(aRegion.mBands);
    mBounds = aRegion.mBounds;
    aRegion.SetEmpty();
    return *this;
  }
  nsRegion& operator=(const nsRect& aRect) {
    Copy(aRect);
    return *this;
  }
  nsRegion& operator=(const nsRegion& aRegion) {
    Copy(aRegion);
    return *this;
  }
  bool operator==(const nsRegion& aRgn) const { return IsEqual(aRgn); }
  bool operator!=(const nsRegion& aRgn) const { return !(*this == aRgn); }

  friend std::ostream& operator<<(std::ostream& stream, const nsRegion& m);
  void OutputToStream(std::string aObjName, std::ostream& stream) const;

 private:
#ifdef DEBUG_REGIONS
  class OperationStringGenerator {
   public:
    virtual ~OperationStringGenerator() = default;

    virtual void OutputOp() = 0;
  };
#endif
 public:
  void AssertStateInternal() const;
  void AssertState() const {
#ifdef DEBUG_REGIONS
    AssertStateInternal();
#endif
  }

 private:
  void And(BandArray& aOut, const BandArray& aIn1, const BandArray& aIn2) {
    size_t idx = 0;
    size_t idxOther = 0;

    // This algorithm essentially forms a new list of bands, by iterating over
    // both regions' lists of band simultaneously, and building a new band
    // wherever the two regions intersect.
    while (true) {
      while (true) {
        while (idx != aIn1.Length() && aIn1[idx].bottom <= aIn2[idxOther].top) {
          // Increment our current band until it ends beyond aOther's current
          // band.
          idx++;
        }

        if (idx == aIn1.Length()) {
          // This region is out of bands, the other region's future bands are
          // ignored.
          break;
        }

        while (idxOther != aIn2.Length() &&
               aIn2[idxOther].bottom <= aIn1[idx].top) {
          // Increment aOther's current band until it ends beyond our current
          // band.
          idxOther++;
        }

        if (idxOther == aIn2.Length()) {
          // The other region's bands are all processed, all our future bands
          // are ignored.
          break;
        }

        if (aIn2[idxOther].top < aIn1[idx].bottom) {
          // We know the other band's bottom lies beyond our band's top because
          // otherwise we would've incremented above. Intersecting bands found.
          break;
        }
      }

      if (idx == aIn1.Length() || idxOther == aIn2.Length()) {
        // The above loop executed a break because we're done.
        break;
      }

      Band newBand(aIn1[idx]);
      // The new band is the intersection of the two current bands from both
      // regions.
      newBand.top = std::max(aIn1[idx].top, aIn2[idxOther].top);
      newBand.bottom = std::min(aIn1[idx].bottom, aIn2[idxOther].bottom);
      newBand.IntersectStrips(aIn2[idxOther]);

      if (newBand.mStrips.Length()) {
        // The intersecting area of the bands had overlapping strips, if it is
        // identical to the band above it merge, otherwise append.
        if (aOut.Length() && aOut.LastElement().bottom == newBand.top &&
            aOut.LastElement().EqualStrips(newBand)) {
          aOut.LastElement().bottom = newBand.bottom;
        } else {
          aOut.AppendElement(std::move(newBand));
        }
      }

      if (aIn2[idxOther].bottom < aIn1[idx].bottom) {
        idxOther++;
        if (idxOther == aIn2.Length()) {
          // Since we will access idxOther the next iteration, check if we're
          // not done.
          break;
        }
      } else {
        // No need to check here since we do at the beginning of the next
        // iteration.
        idx++;
      }
    }
  }

 public:
  nsRegion& AndWith(const nsRegion& aRegion) {
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorAndWith : public OperationStringGenerator {
     public:
      OperationStringGeneratorAndWith(nsRegion& aRegion,
                                      const nsRegion& aOtherRegion)
          : mRegion(&aRegion),
            mRegionCopy(aRegion),
            mOtherRegion(aOtherRegion) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorAndWith() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r1", stream);
        mOtherRegion.OutputToStream("r2", stream);
        stream << "r1.AndWith(r2);\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsRegion mOtherRegion;
    };

    OperationStringGeneratorAndWith opGenerator(*this, aRegion);
#endif
    if (mBounds.IsEmpty()) {
      // Region is empty, stays empty.
      return *this;
    }

    if (aRegion.IsEmpty()) {
      SetEmpty();
      return *this;
    }

    if (aRegion.mBands.IsEmpty()) {
      // Other region is a rect.
      return AndWith(aRegion.mBounds);
    }

    if (mBands.IsEmpty()) {
      mBands.AppendElement(mBounds);
    }

    BandArray newBands;

    And(newBands, mBands, aRegion.mBands);

    mBands = std::move(newBands);
    if (!mBands.Length()) {
      mBounds = nsRectAbsolute();
    } else {
      mBounds = CalculateBounds();
    }

    EnsureSimplified();
    AssertState();
    return *this;
  }

  nsRegion& AndWith(const nsRectAbsolute& aRect) {
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorAndWith : public OperationStringGenerator {
     public:
      OperationStringGeneratorAndWith(nsRegion& aRegion,
                                      const nsRectAbsolute& aRect)
          : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorAndWith() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r", stream);
        stream << "r.AndWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", "
               << mRect.Width() << ", " << mRect.Height() << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsRectAbsolute mRect;
    };

    OperationStringGeneratorAndWith opGenerator(*this, aRect);
#endif
    if (aRect.IsEmpty()) {
      SetEmpty();
      return *this;
    }

    if (mBands.IsEmpty()) {
      mBounds = mBounds.Intersect(aRect);
      return *this;
    }

    size_t idx = 0;

    size_t removeStart = 0;

    // This removes all bands that do not intersect with aRect, and intersects
    // the remaining ones with aRect.

    // Start by figuring out how much to remove from the start.
    while (idx != mBands.Length() && mBands[idx].bottom <= aRect.Y()) {
      idx++;
    }

    // We'll remove these later to avoid needless copying in the array.
    removeStart = idx;

    while (idx != mBands.Length()) {
      if (mBands[idx].top >= aRect.YMost()) {
        mBands.TruncateLength(idx);
        break;
      }

      mBands[idx].top = std::max(mBands[idx].top, aRect.Y());
      mBands[idx].bottom = std::min(mBands[idx].bottom, aRect.YMost());

      mBands[idx].IntersectStrip(Strip(aRect.X(), aRect.XMost()));

      if (!mBands[idx].mStrips.Length()) {
        mBands.RemoveElementAt(idx);
      } else {
        if (idx > removeStart) {
          CompressBefore(idx);
        }
        idx++;
      }
    }

    if (removeStart) {
      mBands.RemoveElementsAt(0, removeStart);
    }

    if (mBands.Length()) {
      mBounds = CalculateBounds();
    } else {
      mBounds.SetEmpty();
    }
    EnsureSimplified();
    AssertState();
    return *this;
  }
  nsRegion& AndWith(const nsRect& aRect) {
    return AndWith(nsRectAbsolute::FromRect(aRect));
  }
  nsRegion& And(const nsRegion& aRgn1, const nsRegion& aRgn2) {
    if (&aRgn1 == this) {
      return AndWith(aRgn2);
    }
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorAnd : public OperationStringGenerator {
     public:
      OperationStringGeneratorAnd(nsRegion& aRegion, const nsRegion& aRegion1,
                                  const nsRegion& aRegion2)
          : mRegion(&aRegion), mRegion1(aRegion1), mRegion2(aRegion2) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorAnd() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegion1.OutputToStream("r1", stream);
        mRegion2.OutputToStream("r2", stream);
        stream << "nsRegion r3;\nr3.And(r1, r2);\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegion1;
      nsRegion mRegion2;
    };

    OperationStringGeneratorAnd opGenerator(*this, aRgn1, aRgn2);
#endif
    mBands.Clear();

    if (aRgn1.IsEmpty() || aRgn2.IsEmpty()) {
      mBounds.SetEmpty();
      return *this;
    }

    if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
      mBounds = aRgn1.mBounds.Intersect(aRgn2.mBounds);
      return *this;
    } else if (aRgn1.mBands.IsEmpty()) {
      return And(aRgn2, aRgn1.mBounds);
    } else if (aRgn2.mBands.IsEmpty()) {
      return And(aRgn1, aRgn2.mBounds);
    }

    And(mBands, aRgn1.mBands, aRgn2.mBands);

    if (!mBands.Length()) {
      mBounds = nsRectAbsolute();
    } else {
      mBounds = CalculateBounds();
    }

    EnsureSimplified();
    AssertState();
    return *this;
  }
  nsRegion& And(const nsRect& aRect, const nsRegion& aRegion) {
    return And(aRegion, aRect);
  }
  nsRegion& And(const nsRegion& aRegion, const nsRectAbsolute& aRect) {
    if (&aRegion == this) {
      return AndWith(aRect);
    }
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorAnd : public OperationStringGenerator {
     public:
      OperationStringGeneratorAnd(nsRegion& aThisRegion,
                                  const nsRegion& aRegion,
                                  const nsRectAbsolute& aRect)
          : mThisRegion(&aThisRegion), mRegion(aRegion), mRect(aRect) {
        aThisRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorAnd() {
        mThisRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegion.OutputToStream("r", stream);
        stream << "nsRegion r2;\nr.And(r2, nsRect(" << mRect.X() << ", "
               << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height()
               << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mThisRegion;
      nsRegion mRegion;
      nsRectAbsolute mRect;
    };

    OperationStringGeneratorAnd opGenerator(*this, aRegion, aRect);
#endif
    mBands.Clear();

    if (aRect.IsEmpty()) {
      mBounds.SetEmpty();
      return *this;
    }

    if (aRegion.mBands.IsEmpty()) {
      mBounds = aRegion.mBounds.Intersect(aRect);
      return *this;
    }

    size_t idx = 0;
    const BandArray& bands = aRegion.mBands;

    mBands.SetCapacity(bands.Length() + 3);
    while (idx != bands.Length()) {
      // Ignore anything before.
      if (bands[idx].bottom <= aRect.Y()) {
        idx++;
        continue;
      }
      // We're done once we've reached the bottom.
      if (bands[idx].top >= aRect.YMost()) {
        break;
      }

      // Now deal with bands actually intersecting the rectangle.
      Band newBand(bands[idx]);
      newBand.top = std::max(bands[idx].top, aRect.Y());
      newBand.bottom = std::min(bands[idx].bottom, aRect.YMost());

      newBand.IntersectStrip(Strip(aRect.X(), aRect.XMost()));

      if (newBand.mStrips.Length()) {
        if (!mBands.IsEmpty() && newBand.top == mBands.LastElement().bottom &&
            newBand.EqualStrips(mBands.LastElement())) {
          mBands.LastElement().bottom = newBand.bottom;
        } else {
          mBands.AppendElement(std::move(newBand));
        }
      }
      idx++;
    }

    if (mBands.Length()) {
      mBounds = CalculateBounds();
    } else {
      mBounds.SetEmpty();
    }

    EnsureSimplified();
    AssertState();
    return *this;
  }
  nsRegion& And(const nsRegion& aRegion, const nsRect& aRect) {
    return And(aRegion, nsRectAbsolute::FromRect(aRect));
  }
  nsRegion& And(const nsRect& aRect1, const nsRect& aRect2) {
    nsRect tmpRect;

    tmpRect.IntersectRect(aRect1, aRect2);
    return Copy(tmpRect);
  }

  nsRegion& OrWith(const nsRegion& aOther) {
    for (RectIterator idx(aOther); !idx.Done(); idx.Next()) {
      AddRect(idx.GetAbsolute());
    }
    return *this;
  }
  nsRegion& OrWith(const nsRect& aOther) {
    AddRect(nsRectAbsolute::FromRect(aOther));
    return *this;
  }
  nsRegion& Or(const nsRegion& aRgn1, const nsRegion& aRgn2) {
    if (&aRgn1 != this) {
      *this = aRgn1;
    }
    for (RectIterator idx(aRgn2); !idx.Done(); idx.Next()) {
      AddRect(idx.GetAbsolute());
    }
    return *this;
  }
  nsRegion& Or(const nsRegion& aRegion, const nsRect& aRect) {
    if (&aRegion != this) {
      *this = aRegion;
    }
    AddRect(nsRectAbsolute::FromRect(aRect));
    return *this;
  }
  nsRegion& Or(const nsRect& aRect, const nsRegion& aRegion) {
    return Or(aRegion, aRect);
  }
  nsRegion& Or(const nsRect& aRect1, const nsRect& aRect2) {
    Copy(aRect1);
    return Or(*this, aRect2);
  }

  nsRegion& XorWith(const nsRegion& aOther) { return Xor(*this, aOther); }
  nsRegion& XorWith(const nsRect& aOther) { return Xor(*this, aOther); }
  nsRegion& Xor(const nsRegion& aRgn1, const nsRegion& aRgn2) {
    // this could be implemented better if pixman had direct
    // support for xoring regions.
    nsRegion p;
    p.Sub(aRgn1, aRgn2);
    nsRegion q;
    q.Sub(aRgn2, aRgn1);
    return Or(p, q);
  }
  nsRegion& Xor(const nsRegion& aRegion, const nsRect& aRect) {
    return Xor(aRegion, nsRegion(aRect));
  }
  nsRegion& Xor(const nsRect& aRect, const nsRegion& aRegion) {
    return Xor(nsRegion(aRect), aRegion);
  }
  nsRegion& Xor(const nsRect& aRect1, const nsRect& aRect2) {
    return Xor(nsRegion(aRect1), nsRegion(aRect2));
  }

  nsRegion ToAppUnits(nscoord aAppUnitsPerPixel) const;

  nsRegion& SubWith(const nsRegion& aOther) {
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorSubWith : public OperationStringGenerator {
     public:
      OperationStringGeneratorSubWith(nsRegion& aRegion,
                                      const nsRegion& aOtherRegion)
          : mRegion(&aRegion),
            mRegionCopy(aRegion),
            mOtherRegion(aOtherRegion) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorSubWith() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r1", stream);
        mOtherRegion.OutputToStream("r2", stream);
        stream << "r1.SubWith(r2);\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsRegion mOtherRegion;
    };

    OperationStringGeneratorSubWith opGenerator(*this, aOther);
#endif

    if (mBounds.IsEmpty()) {
      return *this;
    }

    if (aOther.mBands.IsEmpty()) {
      return SubWith(aOther.mBounds);
    }

    if (mBands.IsEmpty()) {
      mBands.AppendElement(Band(mBounds));
    }

    size_t idx = 0;
    size_t idxOther = 0;
    while (idx < mBands.Length()) {
      while (true) {
        while (idx != mBands.Length() &&
               mBands[idx].bottom <= aOther.mBands[idxOther].top) {
          // Increment our current band until it ends beyond aOther's current
          // band.
          idx++;
        }

        if (idx == mBands.Length()) {
          // This region is out of bands, the other region's future bands are
          // ignored.
          break;
        }

        while (idxOther != aOther.mBands.Length() &&
               aOther.mBands[idxOther].bottom <= mBands[idx].top) {
          // Increment aOther's current band until it ends beyond our current
          // band.
          idxOther++;
        }

        if (idxOther == aOther.mBands.Length()) {
          // The other region's bands are all processed, all our future bands
          // are ignored.
          break;
        }

        if (aOther.mBands[idxOther].top < mBands[idx].bottom) {
          // We know the other band's bottom lies beyond our band's top because
          // otherwise we would've incremented above. Intersecting bands found.
          break;
        }
      }

      if (idx == mBands.Length() || idxOther == aOther.mBands.Length()) {
        // The above loop executed a break because we're done.
        break;
      }

      const Band& bandOther = aOther.mBands[idxOther];

      if (!mBands[idx].Intersects(bandOther)) {
        if (mBands[idx].bottom < bandOther.bottom) {
          idx++;
        } else {
          idxOther++;
          if (idxOther == aOther.mBands.Length()) {
            break;
          }
        }
        continue;
      }

      // These bands actually intersect.
      if (mBands[idx].top < bandOther.top) {
        mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
        mBands[idx].bottom = bandOther.top;
        idx++;
        mBands[idx].top = bandOther.top;
      }

      // mBands[idx].top >= bandOther.top;
      if (mBands[idx].bottom <= bandOther.bottom) {
        mBands[idx].SubStrips(bandOther);
        if (mBands[idx].mStrips.IsEmpty()) {
          mBands.RemoveElementAt(idx);
        } else {
          CompressBefore(idx);
          idx++;
          // The band before us just changed, it may be identical now.
          CompressBefore(idx);
        }
        continue;
      }

      // mBands[idx].bottom > bandOther.bottom
      Band newBand = mBands[idx];
      newBand.SubStrips(bandOther);

      if (!newBand.mStrips.IsEmpty()) {
        mBands.InsertElementAt(idx, newBand);
        mBands[idx].bottom = bandOther.bottom;
        CompressBefore(idx);
        idx++;
      }

      mBands[idx].top = bandOther.bottom;

      idxOther++;
      if (idxOther == aOther.mBands.Length()) {
        break;
      }
    }

    if (mBands.IsEmpty()) {
      mBounds.SetEmpty();
    } else {
      mBounds = CalculateBounds();
    }

    AssertState();
    EnsureSimplified();
    return *this;
  }
  nsRegion& SubOut(const nsRegion& aOther) { return SubWith(aOther); }
  nsRegion& SubOut(const nsRect& aOther) { return SubWith(aOther); }

 private:
  void AppendOrExtend(const Band& aNewBand) {
    if (aNewBand.mStrips.IsEmpty()) {
      return;
    }
    if (mBands.IsEmpty()) {
      mBands.AppendElement(aNewBand);
      return;
    }

    if (mBands.LastElement().bottom == aNewBand.top &&
        mBands.LastElement().EqualStrips(aNewBand)) {
      mBands.LastElement().bottom = aNewBand.bottom;
    } else {
      mBands.AppendElement(aNewBand);
    }
  }
  void AppendOrExtend(const Band&& aNewBand) {
    if (aNewBand.mStrips.IsEmpty()) {
      return;
    }
    if (mBands.IsEmpty()) {
      mBands.AppendElement(std::move(aNewBand));
      return;
    }

    if (mBands.LastElement().bottom == aNewBand.top &&
        mBands.LastElement().EqualStrips(aNewBand)) {
      mBands.LastElement().bottom = aNewBand.bottom;
    } else {
      mBands.AppendElement(std::move(aNewBand));
    }
  }

 public:
  nsRegion& Sub(const nsRegion& aRgn1, const nsRegion& aRgn2) {
    if (&aRgn1 == this) {
      return SubWith(aRgn2);
    }
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorSub : public OperationStringGenerator {
     public:
      OperationStringGeneratorSub(nsRegion& aRegion, const nsRegion& aRgn1,
                                  const nsRegion& aRgn2)
          : mRegion(&aRegion), mRegion1(aRgn1), mRegion2(aRgn2) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorSub() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegion1.OutputToStream("r1", stream);
        mRegion2.OutputToStream("r2", stream);
        stream << "nsRegion r3;\nr3.Sub(r1, r2);\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegion1;
      nsRegion mRegion2;
    };

    OperationStringGeneratorSub opGenerator(*this, aRgn1, aRgn2);
#endif

    mBands.Clear();

    if (aRgn1.mBounds.IsEmpty()) {
      mBounds.SetEmpty();
      return *this;
    }

    if (aRgn2.mBounds.IsEmpty()) {
      Copy(aRgn1);
      return *this;
    }

    if (aRgn1.mBands.IsEmpty() && aRgn2.mBands.IsEmpty()) {
      return Sub(aRgn1.mBounds, aRgn2.mBounds);
    } else if (aRgn1.mBands.IsEmpty()) {
      return Sub(aRgn1.mBounds, aRgn2);
    } else if (aRgn2.mBands.IsEmpty()) {
      return Sub(aRgn1, aRgn2.mBounds);
    }

    const BandArray& bands1 = aRgn1.mBands;
    const BandArray& bands2 = aRgn2.mBands;

    size_t idx = 0;
    size_t idxOther = 0;

    // We iterate the source region's bands, subtracting the other regions bands
    // from them as we move them into ours.
    while (idx < bands1.Length()) {
      while (idxOther < bands2.Length() &&
             bands2[idxOther].bottom <= bands1[idx].top) {
        // These other bands are irrelevant as they don't intersect with the
        // band we're currently processing.
        idxOther++;
      }
      if (idxOther == bands2.Length()) {
        break;
      }

      const Band& other = bands2[idxOther];

      // bands2[idxOther].bottom >= bands1[idx].top
      Band origBand(bands1[idx]);
      if (other.top >= origBand.bottom) {
        // No intersecting bands, append and continue.
        AppendOrExtend(origBand);
        idx++;
        continue;
      }

      // Push a band for an uncovered region above our band.
      if (origBand.top < other.top) {
        Band newBand(origBand);
        newBand.bottom = other.top;
        AppendOrExtend(std::move(newBand));
      }

      int32_t lastBottom = std::max(other.top, origBand.top);
      while (idxOther < bands2.Length() &&
             bands2[idxOther].top < origBand.bottom) {
        const Band& other = bands2[idxOther];
        Band newBand(origBand);
        newBand.top = std::max(origBand.top, other.top);
        newBand.bottom = std::min(origBand.bottom, other.bottom);

        // If there was a gap, we need to add the original band there.
        if (newBand.top > lastBottom) {
          Band betweenBand(newBand);
          betweenBand.top = lastBottom;
          betweenBand.bottom = newBand.top;
          AppendOrExtend(std::move(betweenBand));
        }

        lastBottom = newBand.bottom;
        newBand.SubStrips(other);
        AppendOrExtend(std::move(newBand));
        idxOther++;
      }
      // Decrement other here so we are back at the last band in region 2
      // that intersected.
      idxOther--;

      if (bands2[idxOther].bottom < origBand.bottom) {
        // The last band in region2 that intersected ended before this one,
        // we can copy the rest.
        Band newBand(origBand);
        newBand.top = bands2[idxOther].bottom;
        AppendOrExtend(std::move(newBand));
        idxOther++;
      }
      idx++;
    }

    // Copy any remaining bands, the first one may have to be extended to fit
    // the last one added before. The rest can be unconditionally appended.
    if (idx < bands1.Length()) {
      AppendOrExtend(bands1[idx]);
      idx++;
    }

    while (idx < bands1.Length()) {
      mBands.AppendElement(bands1[idx]);
      idx++;
    }

    if (mBands.IsEmpty()) {
      mBounds.SetEmpty();
    } else {
      mBounds = CalculateBounds();
    }

    AssertState();
    EnsureSimplified();
    return *this;
  }

 private:
  // Internal helper for executing subtraction.
  void RunSubtraction(const nsRectAbsolute& aRect) {
    Strip rectStrip(aRect.X(), aRect.XMost());

    size_t idx = 0;

    while (idx < mBands.Length()) {
      if (mBands[idx].top >= aRect.YMost()) {
        return;
      }

      if (mBands[idx].bottom <= aRect.Y()) {
        // This band is entirely before aRect, move on.
        idx++;
        continue;
      }

      if (!mBands[idx].Intersects(Strip(aRect.X(), aRect.XMost()))) {
        // This band does not intersect aRect horizontally. Move on.
        idx++;
        continue;
      }

      // This band intersects with aRect.

      if (mBands[idx].top < aRect.Y()) {
        // This band starts above the start of aRect, split the band into two
        // along the intersection, and continue to the next iteration to process
        // the one that now intersects exactly.
        auto above = mBands.InsertElementAt(idx, Band(mBands[idx]));
        above->bottom = aRect.Y();
        idx++;
        mBands[idx].top = aRect.Y();
        // Continue to run the loop for the next band.
        continue;
      }

      if (mBands[idx].bottom <= aRect.YMost()) {
        // This band ends before the end of aRect.
        mBands[idx].SubStrip(rectStrip);
        if (mBands[idx].mStrips.Length()) {
          CompressAdjacentBands(idx);
        } else {
          mBands.RemoveElementAt(idx);
        }
        continue;
      }

      // This band extends beyond aRect.
      Band newBand = mBands[idx];
      newBand.SubStrip(rectStrip);
      newBand.bottom = aRect.YMost();
      mBands[idx].top = aRect.YMost();

      if (newBand.mStrips.Length()) {
        if (idx && mBands[idx - 1].bottom == newBand.top &&
            newBand.EqualStrips(mBands[idx - 1])) {
          mBands[idx - 1].bottom = aRect.YMost();
        } else {
          mBands.InsertElementAt(idx, std::move(newBand));
        }
      }

      return;
    }
  }

 public:
  nsRegion& SubWith(const nsRectAbsolute& aRect) {
    if (!mBounds.Intersects(aRect)) {
      return *this;
    }

    if (aRect.Contains(mBounds)) {
      SetEmpty();
      return *this;
    }

#ifdef DEBUG_REGIONS
    class OperationStringGeneratorSubWith : public OperationStringGenerator {
     public:
      OperationStringGeneratorSubWith(nsRegion& aRegion,
                                      const nsRectAbsolute& aRect)
          : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorSubWith() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r", stream);
        stream << "r.SubWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", "
               << mRect.Width() << ", " << mRect.Height() << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsRectAbsolute mRect;
    };

    OperationStringGeneratorSubWith opGenerator(*this, aRect);
#endif

    if (mBands.IsEmpty()) {
      mBands.AppendElement(Band(mBounds));
    }

    RunSubtraction(aRect);

    if (aRect.X() <= mBounds.X() || aRect.Y() <= mBounds.Y() ||
        aRect.XMost() >= mBounds.XMost() || aRect.YMost() >= mBounds.YMost()) {
      mBounds = CalculateBounds();
    }
    EnsureSimplified();
    AssertState();
    return *this;
  }
  nsRegion& Sub(const nsRegion& aRegion, const nsRectAbsolute& aRect) {
    if (aRect.Contains(aRegion.mBounds)) {
      SetEmpty();
      return *this;
    }
    if (&aRegion == this) {
      return SubWith(aRect);
    }
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorSub : public OperationStringGenerator {
     public:
      OperationStringGeneratorSub(nsRegion& aRegion,
                                  const nsRegion& aRegionOther,
                                  const nsRectAbsolute& aRect)
          : mRegion(&aRegion), mRegionOther(aRegionOther), mRect(aRect) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorSub() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionOther.OutputToStream("r1", stream);
        stream << "nsRegion r2;\nr2.Sub(r1, nsRect(" << mRect.X() << ", "
               << mRect.Y() << ", " << mRect.Width() << ", " << mRect.Height()
               << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionOther;
      nsRectAbsolute mRect;
    };

    OperationStringGeneratorSub opGenerator(*this, aRegion, aRect);
#endif

    mBands.Clear();

    if (aRegion.mBounds.IsEmpty()) {
      mBounds.SetEmpty();
      return *this;
    }

    if (aRect.IsEmpty()) {
      Copy(aRegion);
      return *this;
    }

    if (aRegion.mBands.IsEmpty()) {
      Copy(aRegion.mBounds);
      return SubWith(aRect);
    }

    const BandArray& bands = aRegion.mBands;

    size_t idx = 0;

    Strip strip(aRect.X(), aRect.XMost());

    mBands.SetCapacity(bands.Length() + 3);

    // Process all bands that lie before aRect.
    while (idx < bands.Length() && bands[idx].bottom <= aRect.Y()) {
      mBands.AppendElement(bands[idx]);
      idx++;
    }

    // This band's bottom lies beyond aRect.
    if (idx < bands.Length() && bands[idx].top < aRect.Y()) {
      Band newBand(bands[idx]);
      if (bands[idx].Intersects(strip)) {
        newBand.bottom = aRect.Y();
      } else {
        idx++;
      }
      mBands.AppendElement(std::move(newBand));
    }

    // This tracks whether the band when we -exit- the next loop intersected the
    // rectangle.
    bool didIntersect = false;

    while (idx < bands.Length() && bands[idx].top < aRect.YMost()) {
      // Process all bands intersecting with aRect.
      if (!bands[idx].Intersects(strip)) {
        AppendOrExtend(bands[idx]);
        idx++;
        didIntersect = false;
        continue;
      }

      didIntersect = true;
      Band newBand(bands[idx]);
      newBand.top = std::max(newBand.top, aRect.Y());
      newBand.bottom = std::min(newBand.bottom, aRect.YMost());
      newBand.SubStrip(strip);
      AppendOrExtend(std::move(newBand));
      idx++;
    }

    if (didIntersect) {
      if (aRect.YMost() < bands[idx - 1].bottom) {
        // If this band does not intersect the loop above has already added the
        // whole unmodified band.
        Band newBand(bands[idx - 1]);
        newBand.top = aRect.YMost();
        AppendOrExtend(std::move(newBand));
      }
    }

    // Now process all bands beyond aRect.
    if (idx < bands.Length()) {
      AppendOrExtend(bands[idx]);
      idx++;
    }

    mBands.AppendElements(bands.Elements() + idx, bands.Length() - idx);

    if (mBands.IsEmpty()) {
      mBounds.SetEmpty();
    } else {
      mBounds = CalculateBounds();
    }

    AssertState();
    EnsureSimplified();
    return *this;
  }
  nsRegion& SubWith(const nsRect& aRect) {
    return SubWith(nsRectAbsolute::FromRect(aRect));
  }
  nsRegion& Sub(const nsRect& aRect, const nsRegion& aRegion) {
    Copy(aRect);
    return SubWith(aRegion);
  }
  nsRegion& Sub(const nsRectAbsolute& aRect, const nsRegion& aRegion) {
    Copy(aRect);
    return SubWith(aRegion);
  }
  nsRegion& Sub(const nsRect& aRect1, const nsRect& aRect2) {
    Copy(aRect1);
    return SubWith(aRect2);
  }
  nsRegion& Sub(const nsRegion& aRegion, const nsRect& aRect) {
    return Sub(aRegion, nsRectAbsolute::FromRect(aRect));
  }
  nsRegion& Sub(const nsRectAbsolute& aRect1, const nsRectAbsolute& aRect2) {
    Copy(aRect1);
    return SubWith(aRect2);
  }

  /**
   * Returns true if the given point is inside the region. A region
   * created from a rect (x=0, y=0, w=100, h=100) will NOT contain
   * the point x=100, y=100.
   */
  bool Contains(int aX, int aY) const {
    if (mBands.IsEmpty()) {
      return mBounds.Contains(aX, aY);
    }

    auto iter = mBands.begin();

    while (iter != mBands.end()) {
      if (iter->bottom <= aY) {
        iter++;
        continue;
      }

      if (iter->top > aY) {
        return false;
      }

      if (iter->ContainsStrip(Strip(aX, aX + 1))) {
        return true;
      }
      return false;
    }
    return false;
  }

  bool Contains(const nsPoint& aPoint) const {
    return Contains(aPoint.x, aPoint.y);
  }

  bool Contains(const nsRectAbsolute& aRect) const {
    if (aRect.IsEmpty()) {
      return false;
    }

    if (mBands.IsEmpty()) {
      return mBounds.Contains(aRect);
    }

    auto iter = mBands.begin();

    while (iter != mBands.end()) {
      if (iter->bottom <= aRect.Y()) {
        iter++;
        continue;
      }

      if (iter->top > aRect.Y()) {
        return false;
      }

      // Now inside the rectangle.
      if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
        return false;
      }

      if (iter->bottom >= aRect.YMost()) {
        return true;
      }

      int32_t lastY = iter->bottom;
      iter++;
      while (iter != mBands.end()) {
        // Bands do not connect.
        if (iter->top != lastY) {
          return false;
        }

        if (!iter->ContainsStrip(Strip(aRect.X(), aRect.XMost()))) {
          return false;
        }

        if (iter->bottom >= aRect.YMost()) {
          return true;
        }

        lastY = iter->bottom;
        iter++;
      }
    }
    return false;
  }
  bool Contains(const nsRect& aRect) const {
    return Contains(nsRectAbsolute::FromRect(aRect));
  }

  bool Contains(const nsRegion& aRgn) const;
  bool Intersects(const nsRectAbsolute& aRect) const;
  bool Intersects(const nsRect& aRect) const {
    return Intersects(nsRectAbsolute::FromRect(aRect));
  }

  void MoveBy(int32_t aXOffset, int32_t aYOffset) {
    MoveBy(nsPoint(aXOffset, aYOffset));
  }
  void MoveBy(nsPoint aPt) {
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorMoveBy : public OperationStringGenerator {
     public:
      OperationStringGeneratorMoveBy(nsRegion& aRegion, const nsPoint& aPoint)
          : mRegion(&aRegion), mRegionCopy(aRegion), mPoint(aPoint) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorMoveBy() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r", stream);
        stream << "r.MoveBy(nsPoint(" << mPoint.x << ", " << mPoint.y
               << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsPoint mPoint;
    };

    OperationStringGeneratorMoveBy opGenerator(*this, aPt);
#endif

    mBounds.MoveBy(aPt);
    for (Band& band : mBands) {
      band.top += aPt.Y();
      band.bottom += aPt.Y();
      for (Strip& strip : band.mStrips) {
        strip.left += aPt.X();
        strip.right += aPt.X();
      }
    }
    AssertState();
  }
  void SetEmpty() {
    mBands.Clear();
    mBounds.SetEmpty();
  }

  nsRegion MovedBy(int32_t aXOffset, int32_t aYOffset) const {
    return MovedBy(nsPoint(aXOffset, aYOffset));
  }
  nsRegion MovedBy(const nsPoint& aPt) const {
    nsRegion copy(*this);
    copy.MoveBy(aPt);
    return copy;
  }

  nsRegion Intersect(const nsRegion& aOther) const {
    nsRegion intersection;
    intersection.And(*this, aOther);
    return intersection;
  }

  void Inflate(const nsMargin& aMargin);

  nsRegion Inflated(const nsMargin& aMargin) const {
    nsRegion copy(*this);
    copy.Inflate(aMargin);
    return copy;
  }

  bool IsEmpty() const { return mBounds.IsEmpty(); }
  bool IsComplex() const { return GetNumRects() > 1; }
  bool IsEqual(const nsRegion& aRegion) const {
    if (!mBounds.IsEqualInterior(aRegion.mBounds)) {
      return false;
    }

    if (mBands.Length() != aRegion.mBands.Length()) {
      return false;
    }

    for (auto iter1 = mBands.begin(), iter2 = aRegion.mBands.begin();
         iter1 != mBands.end(); iter1++, iter2++) {
      if (iter1->top != iter2->top || iter1->bottom != iter2->bottom ||
          !iter1->EqualStrips(*iter2)) {
        return false;
      }
    }

    return true;
  }

  uint32_t GetNumRects() const {
    if (mBands.IsEmpty()) {
      return mBounds.IsEmpty() ? 0 : 1;
    }

    uint32_t rects = 0;

    for (const Band& band : mBands) {
      rects += band.mStrips.Length();
    }

    return rects;
  }
  const nsRect GetBounds() const { return mBounds.ToNSRect(); }
  const nsRectAbsolute GetAbsoluteBounds() const { return mBounds; }
  uint64_t Area() const;

  /**
   * Return this region scaled to a different appunits per pixel (APP) ratio.
   * This applies nsRect::ScaleToOtherAppUnitsRoundOut/In to each rect of the
   * region.
   * @param aFromAPP the APP to scale from
   * @param aToAPP the APP to scale to
   * @note this can turn an empty region into a non-empty region
   */
  [[nodiscard]] nsRegion ScaleToOtherAppUnitsRoundOut(int32_t aFromAPP,
                                                      int32_t aToAPP) const;
  [[nodiscard]] nsRegion ScaleToOtherAppUnitsRoundIn(int32_t aFromAPP,
                                                     int32_t aToAPP) const;
  nsRegion& ScaleRoundOut(float aXScale, float aYScale);
  nsRegion& ScaleInverseRoundOut(float aXScale, float aYScale);
  nsRegion& Transform(const mozilla::gfx::Matrix4x4& aTransform);
  nsIntRegion ScaleToOutsidePixels(float aXScale, float aYScale,
                                   nscoord aAppUnitsPerPixel) const;
  nsIntRegion ScaleToInsidePixels(float aXScale, float aYScale,
                                  nscoord aAppUnitsPerPixel) const;
  nsIntRegion ScaleToNearestPixels(float aXScale, float aYScale,
                                   nscoord aAppUnitsPerPixel) const;
  nsIntRegion ToOutsidePixels(nscoord aAppUnitsPerPixel) const;
  nsIntRegion ToNearestPixels(nscoord aAppUnitsPerPixel) const;

  /**
   * Gets the largest rectangle contained in the region.
   * @param aContainingRect if non-empty, we choose a rectangle that
   * maximizes the area intersecting with aContainingRect (and break ties by
   * then choosing the largest rectangle overall)
   */
  nsRect GetLargestRectangle(const nsRect& aContainingRect = nsRect()) const;

  /**
   * Make sure the region has at most aMaxRects by adding area to it
   * if necessary. The simplified region will be a superset of the
   * original region. The simplified region's bounding box will be
   * the same as for the current region.
   */
  void SimplifyOutward(uint32_t aMaxRects);
  /**
   * Simplify the region by adding at most aThreshold area between spans of
   * rects.  The simplified region will be a superset of the original region.
   * The simplified region's bounding box will be the same as for the current
   * region.
   */
  void SimplifyOutwardByArea(uint32_t aThreshold);
  /**
   * Make sure the region has at most aMaxRects by removing area from
   * it if necessary. The simplified region will be a subset of the
   * original region.
   */
  void SimplifyInward(uint32_t aMaxRects);

  /**
   * VisitEdges is a weird kind of function that we use for padding
   * out surfaces to prevent texture filtering artifacts.
   * It calls the visitFn callback for each of the exterior edges of
   * the regions. The top and bottom edges will be expanded 1 pixel
   * to the left and right if there's an outside corner. The order
   * the edges are visited is not guaranteed.
   *
   * visitFn has a side parameter that can be TOP,BOTTOM,LEFT,RIGHT
   * and specifies which kind of edge is being visited. x1, y1, x2, y2
   * are the coordinates of the line. (x1 == x2) || (y1 == y2)
   */
  typedef void (*visitFn)(void* closure, VisitSide side, int x1, int y1, int x2,
                          int y2);
  void VisitEdges(visitFn, void* closure) const;

  nsCString ToString() const;

  static inline pixman_box32_t RectToBox(const nsRect& aRect) {
    pixman_box32_t box = {aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost()};
    return box;
  }

  static inline pixman_box32_t RectToBox(const mozilla::gfx::IntRect& aRect) {
    pixman_box32_t box = {aRect.X(), aRect.Y(), aRect.XMost(), aRect.YMost()};
    return box;
  }

 private:
  nsIntRegion ToPixels(nscoord aAppUnitsPerPixel, bool aOutsidePixels) const;

  nsRegion& Copy(const nsRegion& aRegion) {
    mBounds = aRegion.mBounds;
    mBands = aRegion.mBands.Clone();
    return *this;
  }

  nsRegion& Copy(const nsRect& aRect) {
    mBands.Clear();
    mBounds = nsRectAbsolute::FromRect(aRect);
    return *this;
  }

  nsRegion& Copy(const nsRectAbsolute& aRect) {
    mBands.Clear();
    mBounds = aRect;
    return *this;
  }

  void EnsureSimplified() {
    if (mBands.Length() == 1 && mBands.begin()->mStrips.Length() == 1) {
      mBands.Clear();
    }
  }

  static inline nsRectAbsolute BoxToRect(const pixman_box32_t& aBox) {
    return nsRectAbsolute(aBox.x1, aBox.y1, aBox.x2, aBox.y2);
  }

  void AddRect(const nsRectAbsolute& aRect) {
#ifdef DEBUG_REGIONS
    class OperationStringGeneratorAddRect : public OperationStringGenerator {
     public:
      OperationStringGeneratorAddRect(nsRegion& aRegion,
                                      const nsRectAbsolute& aRect)
          : mRegion(&aRegion), mRegionCopy(aRegion), mRect(aRect) {
        aRegion.mCurrentOpGenerator = this;
      }
      virtual ~OperationStringGeneratorAddRect() {
        mRegion->mCurrentOpGenerator = nullptr;
      }

      virtual void OutputOp() override {
        std::stringstream stream;
        mRegionCopy.OutputToStream("r", stream);
        stream << "r.OrWith(nsRect(" << mRect.X() << ", " << mRect.Y() << ", "
               << mRect.Width() << ", " << mRect.Height() << "));\n";
        gfxCriticalError() << stream.str();
      }

     private:
      nsRegion* mRegion;
      nsRegion mRegionCopy;
      nsRectAbsolute mRect;
    };

    OperationStringGeneratorAddRect opGenerator(*this, aRect);
#endif
    if (aRect.IsEmpty()) {
      return;
    }

    if (mBands.IsEmpty()) {
      if (mBounds.IsEmpty()) {
        mBounds = aRect;
        return;
      } else if (mBounds.Contains(aRect)) {
        return;
      }

      mBands.AppendElement(Band(mBounds));
    }

    mBounds = aRect.UnsafeUnion(mBounds);

    size_t idx = 0;

    Strip strip(aRect.X(), aRect.XMost());
    Band remaining(aRect);

    while (idx != mBands.Length()) {
      if (mBands[idx].bottom <= remaining.top) {
        // This band lies wholly above aRect.
        idx++;
        continue;
      }

      if (remaining.top >= remaining.bottom) {
        AssertState();
        EnsureSimplified();
        return;
      }

      if (mBands[idx].top >= remaining.bottom) {
        // This band lies wholly below aRect.
        break;
      }

      if (mBands[idx].EqualStrips(remaining)) {
        mBands[idx].top = std::min(mBands[idx].top, remaining.top);
        // Nothing to do for this band. Just expand.
        remaining.top = mBands[idx].bottom;
        CompressBefore(idx);
        idx++;
        continue;
      }

      if (mBands[idx].top > remaining.top) {
        auto before = mBands.InsertElementAt(idx, remaining);
        before->bottom = mBands[idx + 1].top;
        remaining.top = before->bottom;
        CompressBefore(idx);
        idx++;
        CompressBefore(idx);
        continue;
      }

      if (mBands[idx].ContainsStrip(strip)) {
        remaining.top = mBands[idx].bottom;
        idx++;
        continue;
      }

      // mBands[idx].top <= remaining.top.

      if (mBands[idx].top < remaining.top) {
        auto before = mBands.InsertElementAt(idx, Band(mBands[idx]));
        before->bottom = remaining.top;
        idx++;
        mBands[idx].top = remaining.top;
        continue;
      }

      // mBands[idx].top == remaining.top
      if (mBands[idx].bottom > remaining.bottom) {
        auto below = mBands.InsertElementAt(idx + 1, Band(mBands[idx]));
        below->top = remaining.bottom;
        mBands[idx].bottom = remaining.bottom;
      }

      mBands[idx].InsertStrip(strip);
      CompressBefore(idx);
      remaining.top = mBands[idx].bottom;
      idx++;
      CompressBefore(idx);
    }

    if (remaining.top < remaining.bottom) {
      // We didn't find any bands that overlapped aRect.
      if (idx) {
        if (mBands[idx - 1].bottom == remaining.top &&
            mBands[idx - 1].EqualStrips(remaining)) {
          mBands[idx - 1].bottom = remaining.bottom;
          CompressBefore(idx);
          AssertState();
          EnsureSimplified();
          return;
        }
      }
      mBands.InsertElementAt(idx, remaining);
      idx++;
      CompressBefore(idx);
    } else {
      CompressBefore(idx);
    }

    AssertState();
    EnsureSimplified();
  }

  // Most callers could probably do this on the fly, if this ever shows up
  // in profiles we could optimize this.
  nsRectAbsolute CalculateBounds() const {
    if (mBands.IsEmpty()) {
      return mBounds;
    }

    int32_t top = mBands.begin()->top;
    int32_t bottom = mBands.LastElement().bottom;

    int32_t leftMost = mBands.begin()->mStrips.begin()->left;
    int32_t rightMost = mBands.begin()->mStrips.LastElement().right;
    for (const Band& band : mBands) {
      leftMost = std::min(leftMost, band.mStrips.begin()->left);
      rightMost = std::max(rightMost, band.mStrips.LastElement().right);
    }

    return nsRectAbsolute(leftMost, top, rightMost, bottom);
  }

  static uint32_t ComputeMergedAreaIncrease(const Band& aTopBand,
                                            const Band& aBottomBand);

  // Returns true if idx is now referring to the 'next' band
  bool CompressAdjacentBands(size_t& aIdx) {
    if ((aIdx + 1) < mBands.Length()) {
      if (mBands[aIdx + 1].top == mBands[aIdx].bottom &&
          mBands[aIdx + 1].EqualStrips(mBands[aIdx])) {
        mBands[aIdx].bottom = mBands[aIdx + 1].bottom;
        mBands.RemoveElementAt(aIdx + 1);
      }
    }
    if (aIdx) {
      if (mBands[aIdx - 1].bottom == mBands[aIdx].top &&
          mBands[aIdx].EqualStrips(mBands[aIdx - 1])) {
        mBands[aIdx - 1].bottom = mBands[aIdx].bottom;
        mBands.RemoveElementAt(aIdx);
        return true;
      }
    }
    return false;
  }

  void CompressBefore(size_t& aIdx) {
    if (aIdx && aIdx < mBands.Length()) {
      if (mBands[aIdx - 1].bottom == mBands[aIdx].top &&
          mBands[aIdx - 1].EqualStrips(mBands[aIdx])) {
        mBands[aIdx].top = mBands[aIdx - 1].top;
        mBands.RemoveElementAt(aIdx - 1);
        aIdx--;
      }
    }
  }

  BandArray mBands;
  // Considering we only ever OR with nsRects, the bounds should fit in an
  // nsRect as well.
  nsRectAbsolute mBounds;
#ifdef DEBUG_REGIONS
  friend class OperationStringGenerator;
  OperationStringGenerator* mCurrentOpGenerator;
#endif

 public:
  class RectIterator {
    const nsRegion& mRegion;
    typename BandArray::const_iterator mCurrentBand;
    typename StripArray::const_iterator mCurrentStrip;

   public:
    explicit RectIterator(const nsRegion& aRegion)
        : mRegion(aRegion),
          mCurrentBand(aRegion.mBands.begin())
#ifndef DEBUG
          ,
          mCurrentStrip(nullptr)
#endif
    {
      mIsDone = mRegion.mBounds.IsEmpty();
      if (mCurrentBand != aRegion.mBands.end()) {
        mCurrentStrip = mCurrentBand->mStrips.begin();
      }
    }

    bool Done() const { return mIsDone; }

    const nsRect Get() const {
      if (mRegion.mBands.IsEmpty()) {
        return mRegion.GetBounds();
      }
      return nsRect(mCurrentStrip->left, mCurrentBand->top,
                    mCurrentStrip->right - mCurrentStrip->left,
                    mCurrentBand->bottom - mCurrentBand->top);
    }

    const nsRectAbsolute GetAbsolute() const {
      if (mRegion.mBands.IsEmpty()) {
        return mRegion.mBounds;
      }
      return nsRectAbsolute(mCurrentStrip->left, mCurrentBand->top,
                            mCurrentStrip->right, mCurrentBand->bottom);
    }

    void Next() {
      if (mRegion.mBands.IsEmpty()) {
        mIsDone = true;
        return;
      }

      mCurrentStrip++;
      if (mCurrentStrip == mCurrentBand->mStrips.end()) {
        mCurrentBand++;
        if (mCurrentBand != mRegion.mBands.end()) {
          mCurrentStrip = mCurrentBand->mStrips.begin();
        } else {
          mIsDone = true;
        }
      }
    }

    bool mIsDone;
  };

  RectIterator RectIter() const { return RectIterator(*this); }
};

namespace mozilla {
namespace gfx {

/**
 * BaseIntRegions use int32_t coordinates.
 */
template <typename Derived, typename Rect, typename Point, typename Margin>
class BaseIntRegion {
  friend class ::nsRegion;

  // Give access to all specializations of IntRegionTyped, not just ones that
  // derive from this specialization of BaseIntRegion.
  template <typename units>
  friend class IntRegionTyped;

 public:
  typedef Rect RectType;
  typedef Point PointType;
  typedef Margin MarginType;

  BaseIntRegion() = default;
  MOZ_IMPLICIT BaseIntRegion(const Rect& aRect) : mImpl(ToRect(aRect)) {}
  explicit BaseIntRegion(mozilla::gfx::ArrayView<pixman_box32_t> aRects)
      : mImpl(aRects) {}
  BaseIntRegion(const BaseIntRegion& aRegion) : mImpl(aRegion.mImpl) {}
  BaseIntRegion(BaseIntRegion&& aRegion) : mImpl(std::move(aRegion.mImpl)) {}
  Derived& operator=(const Rect& aRect) {
    mImpl = ToRect(aRect);
    return This();
  }
  Derived& operator=(const Derived& aRegion) {
    mImpl = aRegion.mImpl;
    return This();
  }
  Derived& operator=(Derived&& aRegion) {
    mImpl = std::move(aRegion.mImpl);
    return This();
  }

  bool operator==(const Derived& aRgn) const { return IsEqual(aRgn); }
  bool operator!=(const Derived& aRgn) const { return !(*this == aRgn); }

  friend std::ostream& operator<<(std::ostream& stream, const Derived& m) {
    return stream << m.mImpl;
  }

  void AndWith(const Derived& aOther) { And(This(), aOther); }
  void AndWith(const Rect& aOther) { And(This(), aOther); }
  Derived& And(const Derived& aRgn1, const Derived& aRgn2) {
    mImpl.And(aRgn1.mImpl, aRgn2.mImpl);
    return This();
  }
  Derived& And(const Derived& aRegion, const Rect& aRect) {
    mImpl.And(aRegion.mImpl, ToRect(aRect));
    return This();
  }
  Derived& And(const Rect& aRect, const Derived& aRegion) {
    return And(aRegion, aRect);
  }
  Derived& And(const Rect& aRect1, const Rect& aRect2) {
    Rect TmpRect;

    TmpRect.IntersectRect(aRect1, aRect2);
    mImpl = ToRect(TmpRect);
    return This();
  }

  Derived& OrWith(const Derived& aOther) { return Or(This(), aOther); }
  Derived& OrWith(const Rect& aOther) { return Or(This(), aOther); }
  Derived& Or(const Derived& aRgn1, const Derived& aRgn2) {
    mImpl.Or(aRgn1.mImpl, aRgn2.mImpl);
    return This();
  }
  Derived& Or(const Derived& aRegion, const Rect& aRect) {
    mImpl.Or(aRegion.mImpl, ToRect(aRect));
    return This();
  }
  Derived& Or(const Rect& aRect, const Derived& aRegion) {
    return Or(aRegion, aRect);
  }
  Derived& Or(const Rect& aRect1, const Rect& aRect2) {
    mImpl = ToRect(aRect1);
    return Or(This(), aRect2);
  }

  Derived& XorWith(const Derived& aOther) { return Xor(This(), aOther); }
  Derived& XorWith(const Rect& aOther) { return Xor(This(), aOther); }
  Derived& Xor(const Derived& aRgn1, const Derived& aRgn2) {
    mImpl.Xor(aRgn1.mImpl, aRgn2.mImpl);
--> --------------------

--> maximum size reached

--> --------------------