layout/generic/nsTextFrame.cpp
author Noemi Erli <nerli@mozilla.com>
Sat, 12 Jan 2019 00:00:06 +0200
changeset 453615 1ddef6cf6c7ee86191872cac0782b9f6dc01c923
parent 453037 a43422e9e4da8252bf1b48eb05206d0520b06f39
child 454068 d54846d01280026138135bde6e0bb1bcfe58feae
child 454090 036c3b7cde376187c8df91f7d764e528371adace
permissions -rw-r--r--
Merge mozilla-central to inbound. a=merge CLOSED TREE

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

/* rendering object for textual content of elements */

#include "nsTextFrame.h"

#include "gfx2DGlue.h"
#include "gfxPrefs.h"
#include "gfxUtils.h"
#include "mozilla/Attributes.h"
#include "mozilla/ComputedStyle.h"
#include "mozilla/DebugOnly.h"
#include "mozilla/gfx/2D.h"
#include "mozilla/Likely.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/StaticPrefs.h"
#include "mozilla/TextEvents.h"
#include "mozilla/BinarySearch.h"
#include "mozilla/IntegerRange.h"
#include "mozilla/Unused.h"
#include "mozilla/PodOperations.h"

#include "nsCOMPtr.h"
#include "nsBlockFrame.h"
#include "nsFontMetrics.h"
#include "nsSplittableFrame.h"
#include "nsLineLayout.h"
#include "nsString.h"
#include "nsUnicharUtils.h"
#include "nsPresContext.h"
#include "nsIContent.h"
#include "nsStyleConsts.h"
#include "nsStyleStruct.h"
#include "nsStyleStructInlines.h"
#include "SVGTextFrame.h"
#include "nsCoord.h"
#include "gfxContext.h"
#include "nsIPresShell.h"
#include "nsTArray.h"
#include "nsCSSPseudoElements.h"
#include "nsCSSFrameConstructor.h"
#include "nsCompatibility.h"
#include "nsCSSColorUtils.h"
#include "nsLayoutUtils.h"
#include "nsDisplayList.h"
#include "nsFrame.h"
#include "nsIMathMLFrame.h"
#include "nsPlaceholderFrame.h"
#include "nsTextFrameUtils.h"
#include "nsTextRunTransformations.h"
#include "MathMLTextRunFactory.h"
#include "nsUnicodeProperties.h"
#include "nsStyleUtil.h"
#include "nsRubyFrame.h"
#include "TextDrawTarget.h"

#include "nsTextFragment.h"
#include "nsGkAtoms.h"
#include "nsFrameSelection.h"
#include "nsRange.h"
#include "nsCSSRendering.h"
#include "nsContentUtils.h"
#include "nsLineBreaker.h"
#include "nsIFrameInlines.h"
#include "mozilla/intl/WordBreaker.h"
#include "mozilla/ServoStyleSet.h"
#include "mozilla/layers/LayersMessages.h"
#include "mozilla/layers/RenderRootStateManager.h"
#include "mozilla/layers/WebRenderBridgeChild.h"
#include "mozilla/webrender/WebRenderAPI.h"
#include "mozilla/layers/StackingContextHelper.h"

#include <algorithm>
#include <limits>
#ifdef ACCESSIBILITY
#include "nsAccessibilityService.h"
#endif

#include "nsPrintfCString.h"

#include "mozilla/gfx/DrawTargetRecording.h"

#include "mozilla/UniquePtr.h"
#include "mozilla/dom/Element.h"
#include "mozilla/LookAndFeel.h"

#include "GeckoProfiler.h"

#ifdef DEBUG
#undef NOISY_REFLOW
#undef NOISY_TRIM
#else
#undef NOISY_REFLOW
#undef NOISY_TRIM
#endif

#ifdef DrawText
#undef DrawText
#endif

using namespace mozilla;
using namespace mozilla::dom;
using namespace mozilla::gfx;
using namespace mozilla::layers;

typedef mozilla::layout::TextDrawTarget TextDrawTarget;

struct TabWidth {
  TabWidth(uint32_t aOffset, uint32_t aWidth)
      : mOffset(aOffset), mWidth(float(aWidth)) {}

  uint32_t mOffset;  // DOM offset relative to the current frame's offset.
  float mWidth;      // extra space to be added at this position (in app units)
};

struct TabWidthStore {
  explicit TabWidthStore(int32_t aValidForContentOffset)
      : mLimit(0), mValidForContentOffset(aValidForContentOffset) {}

  // Apply tab widths to the aSpacing array, which corresponds to characters
  // beginning at aOffset and has length aLength. (Width records outside this
  // range will be ignored.)
  void ApplySpacing(gfxTextRun::PropertyProvider::Spacing* aSpacing,
                    uint32_t aOffset, uint32_t aLength);

  // Offset up to which tabs have been measured; positions beyond this have not
  // been calculated yet but may be appended if needed later.  It's a DOM
  // offset relative to the current frame's offset.
  uint32_t mLimit;

  // Need to recalc tab offsets if frame content offset differs from this.
  int32_t mValidForContentOffset;

  // A TabWidth record for each tab character measured so far.
  nsTArray<TabWidth> mWidths;
};

namespace {

struct TabwidthAdaptor {
  const nsTArray<TabWidth>& mWidths;
  explicit TabwidthAdaptor(const nsTArray<TabWidth>& aWidths)
      : mWidths(aWidths) {}
  uint32_t operator[](size_t aIdx) const { return mWidths[aIdx].mOffset; }
};

}  // namespace

void TabWidthStore::ApplySpacing(
    gfxTextRun::PropertyProvider::Spacing* aSpacing, uint32_t aOffset,
    uint32_t aLength) {
  size_t i = 0;
  const size_t len = mWidths.Length();

  // If aOffset is non-zero, do a binary search to find where to start
  // processing the tab widths, in case the list is really long. (See bug
  // 953247.)
  // We need to start from the first entry where mOffset >= aOffset.
  if (aOffset > 0) {
    mozilla::BinarySearch(TabwidthAdaptor(mWidths), 0, len, aOffset, &i);
  }

  uint32_t limit = aOffset + aLength;
  while (i < len) {
    const TabWidth& tw = mWidths[i];
    if (tw.mOffset >= limit) {
      break;
    }
    aSpacing[tw.mOffset - aOffset].mAfter += tw.mWidth;
    i++;
  }
}

NS_DECLARE_FRAME_PROPERTY_DELETABLE(TabWidthProperty, TabWidthStore)

NS_DECLARE_FRAME_PROPERTY_WITHOUT_DTOR(OffsetToFrameProperty, nsTextFrame)

NS_DECLARE_FRAME_PROPERTY_RELEASABLE(UninflatedTextRunProperty, gfxTextRun)

NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(FontSizeInflationProperty, float)

/**
 * A glyph observer for the change of a font glyph in a text run.
 *
 * This is stored in {Simple, Complex}TextRunUserData.
 */
class GlyphObserver final : public gfxFont::GlyphChangeObserver {
 public:
  GlyphObserver(gfxFont* aFont, gfxTextRun* aTextRun)
      : gfxFont::GlyphChangeObserver(aFont), mTextRun(aTextRun) {
    MOZ_ASSERT(aTextRun->GetUserData());
  }
  void NotifyGlyphsChanged() override;

 private:
  gfxTextRun* mTextRun;
};

static const nsFrameState TEXT_REFLOW_FLAGS =
    TEXT_FIRST_LETTER | TEXT_START_OF_LINE | TEXT_END_OF_LINE |
    TEXT_HYPHEN_BREAK | TEXT_TRIMMED_TRAILING_WHITESPACE |
    TEXT_JUSTIFICATION_ENABLED | TEXT_HAS_NONCOLLAPSED_CHARACTERS |
    TEXT_SELECTION_UNDERLINE_OVERFLOWED | TEXT_NO_RENDERED_GLYPHS;

static const nsFrameState TEXT_WHITESPACE_FLAGS =
    TEXT_IS_ONLY_WHITESPACE | TEXT_ISNOT_ONLY_WHITESPACE;

/*
 * Some general notes
 *
 * Text frames delegate work to gfxTextRun objects. The gfxTextRun object
 * transforms text to positioned glyphs. It can report the geometry of the
 * glyphs and paint them. Text frames configure gfxTextRuns by providing text,
 * spacing, language, and other information.
 *
 * A gfxTextRun can cover more than one DOM text node. This is necessary to
 * get kerning, ligatures and shaping for text that spans multiple text nodes
 * but is all the same font.
 *
 * The userdata for a gfxTextRun object can be:
 *
 *   - A nsTextFrame* in the case a text run maps to only one flow. In this
 *   case, the textrun's user data pointer is a pointer to mStartFrame for that
 *   flow, mDOMOffsetToBeforeTransformOffset is zero, and mContentLength is the
 *   length of the text node.
 *
 *   - A SimpleTextRunUserData in the case a text run maps to one flow, but we
 *   still have to keep a list of glyph observers.
 *
 *   - A ComplexTextRunUserData in the case a text run maps to multiple flows,
 *   but we need to keep a list of glyph observers.
 *
 *   - A TextRunUserData in the case a text run maps multiple flows, but it
 *   doesn't have any glyph observer for changes in SVG fonts.
 *
 * You can differentiate between the four different cases with the
 * TEXT_IS_SIMPLE_FLOW and TEXT_MIGHT_HAVE_GLYPH_CHANGES flags.
 *
 * We go to considerable effort to make sure things work even if in-flow
 * siblings have different ComputedStyles (i.e., first-letter and first-line).
 *
 * Our convention is that unsigned integer character offsets are offsets into
 * the transformed string. Signed integer character offsets are offsets into
 * the DOM string.
 *
 * XXX currently we don't handle hyphenated breaks between text frames where the
 * hyphen occurs at the end of the first text frame, e.g.
 *   <b>Kit&shy;</b>ty
 */

/**
 * This is our user data for the textrun, when textRun->GetFlags2() has
 * TEXT_IS_SIMPLE_FLOW set, and also TEXT_MIGHT_HAVE_GLYPH_CHANGES.
 *
 * This allows having an array of observers if there are fonts whose glyphs
 * might change, but also avoid allocation in the simple case that there aren't.
 */
struct SimpleTextRunUserData {
  nsTArray<UniquePtr<GlyphObserver>> mGlyphObservers;
  nsTextFrame* mFrame;
  explicit SimpleTextRunUserData(nsTextFrame* aFrame) : mFrame(aFrame) {}
};

/**
 * We use an array of these objects to record which text frames
 * are associated with the textrun. mStartFrame is the start of a list of
 * text frames. Some sequence of its continuations are covered by the textrun.
 * A content textnode can have at most one TextRunMappedFlow associated with it
 * for a given textrun.
 *
 * mDOMOffsetToBeforeTransformOffset is added to DOM offsets for those frames to
 * obtain the offset into the before-transformation text of the textrun. It can
 * be positive (when a text node starts in the middle of a text run) or negative
 * (when a text run starts in the middle of a text node). Of course it can also
 * be zero.
 */
struct TextRunMappedFlow {
  nsTextFrame* mStartFrame;
  int32_t mDOMOffsetToBeforeTransformOffset;
  // The text mapped starts at mStartFrame->GetContentOffset() and is this long
  uint32_t mContentLength;
};

/**
 * This is the type in the gfxTextRun's userdata field in the common case that
 * the text run maps to multiple flows, but no fonts have been found with
 * animatable glyphs.
 *
 * This way, we avoid allocating and constructing the extra nsTArray.
 */
struct TextRunUserData {
#ifdef DEBUG
  TextRunMappedFlow* mMappedFlows;
#endif
  uint32_t mMappedFlowCount;
  uint32_t mLastFlowIndex;
};

/**
 * This is our user data for the textrun, when textRun->GetFlags2() does not
 * have TEXT_IS_SIMPLE_FLOW set and has the TEXT_MIGHT HAVE_GLYPH_CHANGES flag.
 */
struct ComplexTextRunUserData : public TextRunUserData {
  nsTArray<UniquePtr<GlyphObserver>> mGlyphObservers;
};

/**
 * This helper object computes colors used for painting, and also IME
 * underline information. The data is computed lazily and cached as necessary.
 * These live for just the duration of one paint operation.
 */
class nsTextPaintStyle {
 public:
  explicit nsTextPaintStyle(nsTextFrame* aFrame);

  void SetResolveColors(bool aResolveColors) {
    mResolveColors = aResolveColors;
  }

  nscolor GetTextColor();

  // SVG text has its own painting process, so we should never get its stroke
  // property from here.
  nscolor GetWebkitTextStrokeColor() {
    if (nsSVGUtils::IsInSVGTextSubtree(mFrame)) {
      return 0;
    }
    return mFrame->StyleText()->mWebkitTextStrokeColor.CalcColor(mFrame);
  }
  float GetWebkitTextStrokeWidth() {
    if (nsSVGUtils::IsInSVGTextSubtree(mFrame)) {
      return 0.0f;
    }
    nscoord coord = mFrame->StyleText()->mWebkitTextStrokeWidth;
    return mFrame->PresContext()->AppUnitsToFloatDevPixels(coord);
  }

  /**
   * Compute the colors for normally-selected text. Returns false if
   * the normal selection is not being displayed.
   */
  bool GetSelectionColors(nscolor* aForeColor, nscolor* aBackColor);
  void GetHighlightColors(nscolor* aForeColor, nscolor* aBackColor);
  void GetURLSecondaryColor(nscolor* aForeColor);
  void GetIMESelectionColors(int32_t aIndex, nscolor* aForeColor,
                             nscolor* aBackColor);
  // if this returns false, we don't need to draw underline.
  bool GetSelectionUnderlineForPaint(int32_t aIndex, nscolor* aLineColor,
                                     float* aRelativeSize, uint8_t* aStyle);

  // if this returns false, we don't need to draw underline.
  static bool GetSelectionUnderline(nsPresContext* aPresContext, int32_t aIndex,
                                    nscolor* aLineColor, float* aRelativeSize,
                                    uint8_t* aStyle);

  // if this returns false, no text-shadow was specified for the selection
  // and the *aShadow parameter was not modified.
  bool GetSelectionShadow(nsCSSShadowArray** aShadow);

  nsPresContext* PresContext() const { return mPresContext; }

  enum {
    eIndexRawInput = 0,
    eIndexSelRawText,
    eIndexConvText,
    eIndexSelConvText,
    eIndexSpellChecker
  };

  static int32_t GetUnderlineStyleIndexForSelectionType(
      SelectionType aSelectionType) {
    switch (aSelectionType) {
      case SelectionType::eIMERawClause:
        return eIndexRawInput;
      case SelectionType::eIMESelectedRawClause:
        return eIndexSelRawText;
      case SelectionType::eIMEConvertedClause:
        return eIndexConvText;
      case SelectionType::eIMESelectedClause:
        return eIndexSelConvText;
      case SelectionType::eSpellCheck:
        return eIndexSpellChecker;
      default:
        NS_WARNING("non-IME selection type");
        return eIndexRawInput;
    }
  }

  nscolor GetSystemFieldForegroundColor();
  nscolor GetSystemFieldBackgroundColor();

 protected:
  nsTextFrame* mFrame;
  nsPresContext* mPresContext;
  bool mInitCommonColors;
  bool mInitSelectionColorsAndShadow;
  bool mResolveColors;

  // Selection data

  nscolor mSelectionTextColor;
  nscolor mSelectionBGColor;
  RefPtr<nsCSSShadowArray> mSelectionShadow;
  bool mHasSelectionShadow;

  // Common data

  int32_t mSufficientContrast;
  nscolor mFrameBackgroundColor;
  nscolor mSystemFieldForegroundColor;
  nscolor mSystemFieldBackgroundColor;

  // selection colors and underline info, the colors are resolved colors if
  // mResolveColors is true (which is the default), i.e., the foreground color
  // and background color are swapped if it's needed. And also line color will
  // be resolved from them.
  struct nsSelectionStyle {
    bool mInit;
    nscolor mTextColor;
    nscolor mBGColor;
    nscolor mUnderlineColor;
    uint8_t mUnderlineStyle;
    float mUnderlineRelativeSize;
  };
  nsSelectionStyle mSelectionStyle[5];

  // Color initializations
  void InitCommonColors();
  bool InitSelectionColorsAndShadow();

  nsSelectionStyle* GetSelectionStyle(int32_t aIndex);
  void InitSelectionStyle(int32_t aIndex);

  // Ensures sufficient contrast between the frame background color and the
  // selection background color, and swaps the selection text and background
  // colors accordingly.
  // Only used on platforms where mSelectionTextColor != NS_DONT_CHANGE_COLOR
  bool EnsureSufficientContrast(nscolor* aForeColor, nscolor* aBackColor);

  nscolor GetResolvedForeColor(nscolor aColor, nscolor aDefaultForeColor,
                               nscolor aBackColor);
};

static TextRunUserData* CreateUserData(uint32_t aMappedFlowCount) {
  TextRunUserData* data = static_cast<TextRunUserData*>(moz_xmalloc(
      sizeof(TextRunUserData) + aMappedFlowCount * sizeof(TextRunMappedFlow)));
#ifdef DEBUG
  data->mMappedFlows = reinterpret_cast<TextRunMappedFlow*>(data + 1);
#endif
  data->mMappedFlowCount = aMappedFlowCount;
  data->mLastFlowIndex = 0;
  return data;
}

static void DestroyUserData(TextRunUserData* aUserData) {
  if (aUserData) {
    free(aUserData);
  }
}

static ComplexTextRunUserData* CreateComplexUserData(
    uint32_t aMappedFlowCount) {
  ComplexTextRunUserData* data = static_cast<ComplexTextRunUserData*>(
      moz_xmalloc(sizeof(ComplexTextRunUserData) +
                  aMappedFlowCount * sizeof(TextRunMappedFlow)));
  new (data) ComplexTextRunUserData();
#ifdef DEBUG
  data->mMappedFlows = reinterpret_cast<TextRunMappedFlow*>(data + 1);
#endif
  data->mMappedFlowCount = aMappedFlowCount;
  data->mLastFlowIndex = 0;
  return data;
}

static void DestroyComplexUserData(ComplexTextRunUserData* aUserData) {
  if (aUserData) {
    aUserData->~ComplexTextRunUserData();
    free(aUserData);
  }
}

static void DestroyTextRunUserData(gfxTextRun* aTextRun) {
  MOZ_ASSERT(aTextRun->GetUserData());
  if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    if (aTextRun->GetFlags2() &
        nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES) {
      delete static_cast<SimpleTextRunUserData*>(aTextRun->GetUserData());
    }
  } else {
    if (aTextRun->GetFlags2() &
        nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES) {
      DestroyComplexUserData(
          static_cast<ComplexTextRunUserData*>(aTextRun->GetUserData()));
    } else {
      DestroyUserData(static_cast<TextRunUserData*>(aTextRun->GetUserData()));
    }
  }
  aTextRun->ClearFlagBits(
      nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES);
  aTextRun->SetUserData(nullptr);
}

static TextRunMappedFlow* GetMappedFlows(const gfxTextRun* aTextRun) {
  MOZ_ASSERT(aTextRun->GetUserData(), "UserData must exist.");
  MOZ_ASSERT(
      !(aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW),
      "The method should not be called for simple flows.");
  TextRunMappedFlow* flows;
  if (aTextRun->GetFlags2() &
      nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES) {
    flows = reinterpret_cast<TextRunMappedFlow*>(
        static_cast<ComplexTextRunUserData*>(aTextRun->GetUserData()) + 1);
  } else {
    flows = reinterpret_cast<TextRunMappedFlow*>(
        static_cast<TextRunUserData*>(aTextRun->GetUserData()) + 1);
  }
  MOZ_ASSERT(
      static_cast<TextRunUserData*>(aTextRun->GetUserData())->mMappedFlows ==
          flows,
      "GetMappedFlows should return the same pointer as mMappedFlows.");
  return flows;
}

/**
 * These are utility functions just for helping with the complexity related with
 * the text runs user data.
 */
static nsTextFrame* GetFrameForSimpleFlow(const gfxTextRun* aTextRun) {
  MOZ_ASSERT(
      aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW,
      "Not so simple flow?");
  if (aTextRun->GetFlags2() &
      nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES) {
    return static_cast<SimpleTextRunUserData*>(aTextRun->GetUserData())->mFrame;
  }

  return static_cast<nsTextFrame*>(aTextRun->GetUserData());
}

/**
 * Remove |aTextRun| from the frame continuation chain starting at
 * |aStartContinuation| if non-null, otherwise starting at |aFrame|.
 * Unmark |aFrame| as a text run owner if it's the frame we start at.
 * Return true if |aStartContinuation| is non-null and was found
 * in the next-continuation chain of |aFrame|.
 */
static bool ClearAllTextRunReferences(nsTextFrame* aFrame, gfxTextRun* aTextRun,
                                      nsTextFrame* aStartContinuation,
                                      nsFrameState aWhichTextRunState) {
  MOZ_ASSERT(aFrame, "null frame");
  MOZ_ASSERT(!aStartContinuation ||
                 (!aStartContinuation->GetTextRun(nsTextFrame::eInflated) ||
                  aStartContinuation->GetTextRun(nsTextFrame::eInflated) ==
                      aTextRun) ||
                 (!aStartContinuation->GetTextRun(nsTextFrame::eNotInflated) ||
                  aStartContinuation->GetTextRun(nsTextFrame::eNotInflated) ==
                      aTextRun),
             "wrong aStartContinuation for this text run");

  if (!aStartContinuation || aStartContinuation == aFrame) {
    aFrame->RemoveStateBits(aWhichTextRunState);
  } else {
    do {
      NS_ASSERTION(aFrame->IsTextFrame(), "Bad frame");
      aFrame = aFrame->GetNextContinuation();
    } while (aFrame && aFrame != aStartContinuation);
  }
  bool found = aStartContinuation == aFrame;
  while (aFrame) {
    NS_ASSERTION(aFrame->IsTextFrame(), "Bad frame");
    if (!aFrame->RemoveTextRun(aTextRun)) {
      break;
    }
    aFrame = aFrame->GetNextContinuation();
  }

  MOZ_ASSERT(!found || aStartContinuation, "how did we find null?");
  return found;
}

/**
 * Kill all references to |aTextRun| starting at |aStartContinuation|.
 * It could be referenced by any of its owners, and all their in-flows.
 * If |aStartContinuation| is null then process all userdata frames
 * and their continuations.
 * @note the caller is expected to take care of possibly destroying the
 * text run if all userdata frames were reset (userdata is deallocated
 * by this function though). The caller can detect this has occured by
 * checking |aTextRun->GetUserData() == nullptr|.
 */
static void UnhookTextRunFromFrames(gfxTextRun* aTextRun,
                                    nsTextFrame* aStartContinuation) {
  if (!aTextRun->GetUserData()) {
    return;
  }

  if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    nsTextFrame* userDataFrame = GetFrameForSimpleFlow(aTextRun);
    nsFrameState whichTextRunState =
        userDataFrame->GetTextRun(nsTextFrame::eInflated) == aTextRun
            ? TEXT_IN_TEXTRUN_USER_DATA
            : TEXT_IN_UNINFLATED_TEXTRUN_USER_DATA;
    DebugOnly<bool> found = ClearAllTextRunReferences(
        userDataFrame, aTextRun, aStartContinuation, whichTextRunState);
    NS_ASSERTION(!aStartContinuation || found,
                 "aStartContinuation wasn't found in simple flow text run");
    if (!(userDataFrame->GetStateBits() & whichTextRunState)) {
      DestroyTextRunUserData(aTextRun);
    }
  } else {
    auto userData = static_cast<TextRunUserData*>(aTextRun->GetUserData());
    TextRunMappedFlow* userMappedFlows = GetMappedFlows(aTextRun);
    int32_t destroyFromIndex = aStartContinuation ? -1 : 0;
    for (uint32_t i = 0; i < userData->mMappedFlowCount; ++i) {
      nsTextFrame* userDataFrame = userMappedFlows[i].mStartFrame;
      nsFrameState whichTextRunState =
          userDataFrame->GetTextRun(nsTextFrame::eInflated) == aTextRun
              ? TEXT_IN_TEXTRUN_USER_DATA
              : TEXT_IN_UNINFLATED_TEXTRUN_USER_DATA;
      bool found = ClearAllTextRunReferences(
          userDataFrame, aTextRun, aStartContinuation, whichTextRunState);
      if (found) {
        if (userDataFrame->GetStateBits() & whichTextRunState) {
          destroyFromIndex = i + 1;
        } else {
          destroyFromIndex = i;
        }
        aStartContinuation = nullptr;
      }
    }
    NS_ASSERTION(destroyFromIndex >= 0,
                 "aStartContinuation wasn't found in multi flow text run");
    if (destroyFromIndex == 0) {
      DestroyTextRunUserData(aTextRun);
    } else {
      userData->mMappedFlowCount = uint32_t(destroyFromIndex);
      if (userData->mLastFlowIndex >= uint32_t(destroyFromIndex)) {
        userData->mLastFlowIndex = uint32_t(destroyFromIndex) - 1;
      }
    }
  }
}

static void InvalidateFrameDueToGlyphsChanged(nsIFrame* aFrame) {
  MOZ_ASSERT(aFrame);

  nsIPresShell* shell = aFrame->PresShell();
  for (nsIFrame* f = aFrame; f;
       f = nsLayoutUtils::GetNextContinuationOrIBSplitSibling(f)) {
    f->InvalidateFrame();

    // If this is a non-display text frame within SVG <text>, we need
    // to reflow the SVGTextFrame. (This is similar to reflowing the
    // SVGTextFrame in response to style changes, in
    // SVGTextFrame::DidSetComputedStyle.)
    if (nsSVGUtils::IsInSVGTextSubtree(f) &&
        f->GetStateBits() & NS_FRAME_IS_NONDISPLAY) {
      auto svgTextFrame = static_cast<SVGTextFrame*>(
          nsLayoutUtils::GetClosestFrameOfType(f, LayoutFrameType::SVGText));
      svgTextFrame->ScheduleReflowSVGNonDisplayText(nsIPresShell::eResize);
    } else {
      // Theoretically we could just update overflow areas, perhaps using
      // OverflowChangedTracker, but that would do a bunch of work eagerly that
      // we should probably do lazily here since there could be a lot
      // of text frames affected and we'd like to coalesce the work. So that's
      // not easy to do well.
      shell->FrameNeedsReflow(f, nsIPresShell::eResize, NS_FRAME_IS_DIRTY);
    }
  }
}

void GlyphObserver::NotifyGlyphsChanged() {
  if (mTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    InvalidateFrameDueToGlyphsChanged(GetFrameForSimpleFlow(mTextRun));
    return;
  }

  auto data = static_cast<TextRunUserData*>(mTextRun->GetUserData());
  TextRunMappedFlow* userMappedFlows = GetMappedFlows(mTextRun);
  for (uint32_t i = 0; i < data->mMappedFlowCount; ++i) {
    InvalidateFrameDueToGlyphsChanged(userMappedFlows[i].mStartFrame);
  }
}

int32_t nsTextFrame::GetContentEnd() const {
  nsTextFrame* next = GetNextContinuation();
  return next ? next->GetContentOffset() : mContent->GetText()->GetLength();
}

struct FlowLengthProperty {
  int32_t mStartOffset;
  // The offset of the next fixed continuation after mStartOffset, or
  // of the end of the text if there is none
  int32_t mEndFlowOffset;
};

int32_t nsTextFrame::GetInFlowContentLength() {
  if (!(mState & NS_FRAME_IS_BIDI)) {
    return mContent->TextLength() - mContentOffset;
  }

  FlowLengthProperty* flowLength =
      mContent->HasFlag(NS_HAS_FLOWLENGTH_PROPERTY)
          ? static_cast<FlowLengthProperty*>(
                mContent->GetProperty(nsGkAtoms::flowlength))
          : nullptr;

  /**
   * This frame must start inside the cached flow. If the flow starts at
   * mContentOffset but this frame is empty, logically it might be before the
   * start of the cached flow.
   */
  if (flowLength &&
      (flowLength->mStartOffset < mContentOffset ||
       (flowLength->mStartOffset == mContentOffset &&
        GetContentEnd() > mContentOffset)) &&
      flowLength->mEndFlowOffset > mContentOffset) {
#ifdef DEBUG
    NS_ASSERTION(flowLength->mEndFlowOffset >= GetContentEnd(),
                 "frame crosses fixed continuation boundary");
#endif
    return flowLength->mEndFlowOffset - mContentOffset;
  }

  nsTextFrame* nextBidi = LastInFlow()->GetNextContinuation();
  int32_t endFlow =
      nextBidi ? nextBidi->GetContentOffset() : mContent->TextLength();

  if (!flowLength) {
    flowLength = new FlowLengthProperty;
    if (NS_FAILED(mContent->SetProperty(
            nsGkAtoms::flowlength, flowLength,
            nsINode::DeleteProperty<FlowLengthProperty>))) {
      delete flowLength;
      flowLength = nullptr;
    }
    mContent->SetFlags(NS_HAS_FLOWLENGTH_PROPERTY);
  }
  if (flowLength) {
    flowLength->mStartOffset = mContentOffset;
    flowLength->mEndFlowOffset = endFlow;
  }

  return endFlow - mContentOffset;
}

// Smarter versions of dom::IsSpaceCharacter.
// Unicode is really annoying; sometimes a space character isn't whitespace ---
// when it combines with another character
// So we have several versions of IsSpace for use in different contexts.

static bool IsSpaceCombiningSequenceTail(const nsTextFragment* aFrag,
                                         uint32_t aPos) {
  NS_ASSERTION(aPos <= aFrag->GetLength(), "Bad offset");
  if (!aFrag->Is2b()) return false;
  return nsTextFrameUtils::IsSpaceCombiningSequenceTail(
      aFrag->Get2b() + aPos, aFrag->GetLength() - aPos);
}

// Check whether aPos is a space for CSS 'word-spacing' purposes
static bool IsCSSWordSpacingSpace(const nsTextFragment* aFrag, uint32_t aPos,
                                  const nsTextFrame* aFrame,
                                  const nsStyleText* aStyleText) {
  NS_ASSERTION(aPos < aFrag->GetLength(), "No text for IsSpace!");

  char16_t ch = aFrag->CharAt(aPos);
  switch (ch) {
    case ' ':
    case CH_NBSP:
      return !IsSpaceCombiningSequenceTail(aFrag, aPos + 1);
    case '\r':
    case '\t':
      return !aStyleText->WhiteSpaceIsSignificant();
    case '\n':
      return !aStyleText->NewlineIsSignificant(aFrame);
    default:
      return false;
  }
}

// Check whether the string aChars/aLength starts with space that's
// trimmable according to CSS 'white-space:normal/nowrap'.
static bool IsTrimmableSpace(const char16_t* aChars, uint32_t aLength) {
  NS_ASSERTION(aLength > 0, "No text for IsSpace!");

  char16_t ch = *aChars;
  if (ch == ' ')
    return !nsTextFrameUtils::IsSpaceCombiningSequenceTail(aChars + 1,
                                                           aLength - 1);
  return ch == '\t' || ch == '\f' || ch == '\n' || ch == '\r';
}

// Check whether the character aCh is trimmable according to CSS
// 'white-space:normal/nowrap'
static bool IsTrimmableSpace(char aCh) {
  return aCh == ' ' || aCh == '\t' || aCh == '\f' || aCh == '\n' || aCh == '\r';
}

static bool IsTrimmableSpace(const nsTextFragment* aFrag, uint32_t aPos,
                             const nsStyleText* aStyleText) {
  NS_ASSERTION(aPos < aFrag->GetLength(), "No text for IsSpace!");

  switch (aFrag->CharAt(aPos)) {
    case ' ':
      return !aStyleText->WhiteSpaceIsSignificant() &&
             !IsSpaceCombiningSequenceTail(aFrag, aPos + 1);
    case '\n':
      return !aStyleText->NewlineIsSignificantStyle() &&
             aStyleText->mWhiteSpace != mozilla::StyleWhiteSpace::PreSpace;
    case '\t':
    case '\r':
    case '\f':
      return !aStyleText->WhiteSpaceIsSignificant();
    default:
      return false;
  }
}

static bool IsSelectionSpace(const nsTextFragment* aFrag, uint32_t aPos) {
  NS_ASSERTION(aPos < aFrag->GetLength(), "No text for IsSpace!");
  char16_t ch = aFrag->CharAt(aPos);
  if (ch == ' ' || ch == CH_NBSP)
    return !IsSpaceCombiningSequenceTail(aFrag, aPos + 1);
  return ch == '\t' || ch == '\n' || ch == '\f' || ch == '\r';
}

// Count the amount of trimmable whitespace (as per CSS
// 'white-space:normal/nowrap') in a text fragment. The first
// character is at offset aStartOffset; the maximum number of characters
// to check is aLength. aDirection is -1 or 1 depending on whether we should
// progress backwards or forwards.
static uint32_t GetTrimmableWhitespaceCount(const nsTextFragment* aFrag,
                                            int32_t aStartOffset,
                                            int32_t aLength,
                                            int32_t aDirection) {
  int32_t count = 0;
  if (aFrag->Is2b()) {
    const char16_t* str = aFrag->Get2b() + aStartOffset;
    int32_t fragLen = aFrag->GetLength() - aStartOffset;
    for (; count < aLength; ++count) {
      if (!IsTrimmableSpace(str, fragLen)) break;
      str += aDirection;
      fragLen -= aDirection;
    }
  } else {
    const char* str = aFrag->Get1b() + aStartOffset;
    for (; count < aLength; ++count) {
      if (!IsTrimmableSpace(*str)) break;
      str += aDirection;
    }
  }
  return count;
}

static bool IsAllWhitespace(const nsTextFragment* aFrag, bool aAllowNewline) {
  if (aFrag->Is2b()) return false;
  int32_t len = aFrag->GetLength();
  const char* str = aFrag->Get1b();
  for (int32_t i = 0; i < len; ++i) {
    char ch = str[i];
    if (ch == ' ' || ch == '\t' || ch == '\r' || (ch == '\n' && aAllowNewline))
      continue;
    return false;
  }
  return true;
}

static void ClearObserversFromTextRun(gfxTextRun* aTextRun) {
  if (!(aTextRun->GetFlags2() &
        nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES)) {
    return;
  }

  if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    static_cast<SimpleTextRunUserData*>(aTextRun->GetUserData())
        ->mGlyphObservers.Clear();
  } else {
    static_cast<ComplexTextRunUserData*>(aTextRun->GetUserData())
        ->mGlyphObservers.Clear();
  }
}

static void CreateObserversForAnimatedGlyphs(gfxTextRun* aTextRun) {
  if (!aTextRun->GetUserData()) {
    return;
  }

  ClearObserversFromTextRun(aTextRun);

  nsTArray<gfxFont*> fontsWithAnimatedGlyphs;
  uint32_t numGlyphRuns;
  const gfxTextRun::GlyphRun* glyphRuns = aTextRun->GetGlyphRuns(&numGlyphRuns);
  for (uint32_t i = 0; i < numGlyphRuns; ++i) {
    gfxFont* font = glyphRuns[i].mFont;
    if (font->GlyphsMayChange() && !fontsWithAnimatedGlyphs.Contains(font)) {
      fontsWithAnimatedGlyphs.AppendElement(font);
    }
  }
  if (fontsWithAnimatedGlyphs.IsEmpty()) {
    // NB: Theoretically, we should clear the TEXT_MIGHT_HAVE_GLYPH_CHANGES
    // here. That would involve de-allocating the simple user data struct if
    // present too, and resetting the pointer to the frame. In practice, I
    // don't think worth doing that work here, given the flag's only purpose is
    // to distinguish what kind of user data is there.
    return;
  }

  nsTArray<UniquePtr<GlyphObserver>>* observers;

  if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    // Swap the frame pointer for a just-allocated SimpleTextRunUserData if
    // appropriate.
    if (!(aTextRun->GetFlags2() &
          nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES)) {
      auto frame = static_cast<nsTextFrame*>(aTextRun->GetUserData());
      aTextRun->SetUserData(new SimpleTextRunUserData(frame));
    }

    auto data = static_cast<SimpleTextRunUserData*>(aTextRun->GetUserData());
    observers = &data->mGlyphObservers;
  } else {
    if (!(aTextRun->GetFlags2() &
          nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES)) {
      auto oldData = static_cast<TextRunUserData*>(aTextRun->GetUserData());
      TextRunMappedFlow* oldMappedFlows = GetMappedFlows(aTextRun);
      ComplexTextRunUserData* data =
          CreateComplexUserData(oldData->mMappedFlowCount);
      TextRunMappedFlow* dataMappedFlows =
          reinterpret_cast<TextRunMappedFlow*>(data + 1);
      data->mLastFlowIndex = oldData->mLastFlowIndex;
      for (uint32_t i = 0; i < oldData->mMappedFlowCount; ++i) {
        dataMappedFlows[i] = oldMappedFlows[i];
      }
      DestroyUserData(oldData);
      aTextRun->SetUserData(data);
    }
    auto data = static_cast<ComplexTextRunUserData*>(aTextRun->GetUserData());
    observers = &data->mGlyphObservers;
  }

  aTextRun->SetFlagBits(nsTextFrameUtils::Flags::TEXT_MIGHT_HAVE_GLYPH_CHANGES);

  for (auto font : fontsWithAnimatedGlyphs) {
    observers->AppendElement(new GlyphObserver(font, aTextRun));
  }
}

/**
 * This class accumulates state as we scan a paragraph of text. It detects
 * textrun boundaries (changes from text to non-text, hard
 * line breaks, and font changes) and builds a gfxTextRun at each boundary.
 * It also detects linebreaker run boundaries (changes from text to non-text,
 * and hard line breaks) and at each boundary runs the linebreaker to compute
 * potential line breaks. It also records actual line breaks to store them in
 * the textruns.
 */
class BuildTextRunsScanner {
 public:
  BuildTextRunsScanner(nsPresContext* aPresContext, DrawTarget* aDrawTarget,
                       nsIFrame* aLineContainer,
                       nsTextFrame::TextRunType aWhichTextRun)
      : mDrawTarget(aDrawTarget),
        mLineContainer(aLineContainer),
        mCommonAncestorWithLastFrame(nullptr),
        mMissingFonts(aPresContext->MissingFontRecorder()),
        mBidiEnabled(aPresContext->BidiEnabled()),
        mStartOfLine(true),
        mSkipIncompleteTextRuns(false),
        mCanStopOnThisLine(false),
        mWhichTextRun(aWhichTextRun),
        mNextRunContextInfo(nsTextFrameUtils::INCOMING_NONE),
        mCurrentRunContextInfo(nsTextFrameUtils::INCOMING_NONE) {
    ResetRunInfo();
  }
  ~BuildTextRunsScanner() {
    NS_ASSERTION(mBreakSinks.IsEmpty(), "Should have been cleared");
    NS_ASSERTION(mLineBreakBeforeFrames.IsEmpty(), "Should have been cleared");
    NS_ASSERTION(mMappedFlows.IsEmpty(), "Should have been cleared");
  }

  void SetAtStartOfLine() {
    mStartOfLine = true;
    mCanStopOnThisLine = false;
  }
  void SetSkipIncompleteTextRuns(bool aSkip) {
    mSkipIncompleteTextRuns = aSkip;
  }
  void SetCommonAncestorWithLastFrame(nsIFrame* aFrame) {
    mCommonAncestorWithLastFrame = aFrame;
  }
  bool CanStopOnThisLine() { return mCanStopOnThisLine; }
  nsIFrame* GetCommonAncestorWithLastFrame() {
    return mCommonAncestorWithLastFrame;
  }
  void LiftCommonAncestorWithLastFrameToParent(nsIFrame* aFrame) {
    if (mCommonAncestorWithLastFrame &&
        mCommonAncestorWithLastFrame->GetParent() == aFrame) {
      mCommonAncestorWithLastFrame = aFrame;
    }
  }
  void ScanFrame(nsIFrame* aFrame);
  bool IsTextRunValidForMappedFlows(const gfxTextRun* aTextRun);
  void FlushFrames(bool aFlushLineBreaks, bool aSuppressTrailingBreak);
  void FlushLineBreaks(gfxTextRun* aTrailingTextRun);
  void ResetRunInfo() {
    mLastFrame = nullptr;
    mMappedFlows.Clear();
    mLineBreakBeforeFrames.Clear();
    mMaxTextLength = 0;
    mDoubleByteText = false;
  }
  void AccumulateRunInfo(nsTextFrame* aFrame);
  /**
   * @return null to indicate either textrun construction failed or
   * we constructed just a partial textrun to set up linebreaker and other
   * state for following textruns.
   */
  already_AddRefed<gfxTextRun> BuildTextRunForFrames(void* aTextBuffer);
  bool SetupLineBreakerContext(gfxTextRun* aTextRun);
  void AssignTextRun(gfxTextRun* aTextRun, float aInflation);
  nsTextFrame* GetNextBreakBeforeFrame(uint32_t* aIndex);
  void SetupBreakSinksForTextRun(gfxTextRun* aTextRun, const void* aTextPtr);
  void SetupTextEmphasisForTextRun(gfxTextRun* aTextRun, const void* aTextPtr);
  struct FindBoundaryState {
    nsIFrame* mStopAtFrame;
    nsTextFrame* mFirstTextFrame;
    nsTextFrame* mLastTextFrame;
    bool mSeenTextRunBoundaryOnLaterLine;
    bool mSeenTextRunBoundaryOnThisLine;
    bool mSeenSpaceForLineBreakingOnThisLine;
    nsTArray<char16_t>& mBuffer;
  };
  enum FindBoundaryResult {
    FB_CONTINUE,
    FB_STOPPED_AT_STOP_FRAME,
    FB_FOUND_VALID_TEXTRUN_BOUNDARY
  };
  FindBoundaryResult FindBoundaries(nsIFrame* aFrame,
                                    FindBoundaryState* aState);

  bool ContinueTextRunAcrossFrames(nsTextFrame* aFrame1, nsTextFrame* aFrame2);

  // Like TextRunMappedFlow but with some differences. mStartFrame to mEndFrame
  // (exclusive) are a sequence of in-flow frames (if mEndFrame is null, then
  // continuations starting from mStartFrame are a sequence of in-flow frames).
  struct MappedFlow {
    nsTextFrame* mStartFrame;
    nsTextFrame* mEndFrame;
    // When we consider breaking between elements, the nearest common
    // ancestor of the elements containing the characters is the one whose
    // CSS 'white-space' property governs. So this records the nearest common
    // ancestor of mStartFrame and the previous text frame, or null if there
    // was no previous text frame on this line.
    nsIFrame* mAncestorControllingInitialBreak;

    int32_t GetContentEnd() {
      return mEndFrame ? mEndFrame->GetContentOffset()
                       : mStartFrame->GetContent()->GetText()->GetLength();
    }
  };

  class BreakSink final : public nsILineBreakSink {
   public:
    BreakSink(gfxTextRun* aTextRun, DrawTarget* aDrawTarget,
              uint32_t aOffsetIntoTextRun)
        : mTextRun(aTextRun),
          mDrawTarget(aDrawTarget),
          mOffsetIntoTextRun(aOffsetIntoTextRun) {}

    void SetBreaks(uint32_t aOffset, uint32_t aLength,
                   uint8_t* aBreakBefore) final {
      gfxTextRun::Range range(aOffset + mOffsetIntoTextRun,
                              aOffset + mOffsetIntoTextRun + aLength);
      if (mTextRun->SetPotentialLineBreaks(range, aBreakBefore)) {
        // Be conservative and assume that some breaks have been set
        mTextRun->ClearFlagBits(nsTextFrameUtils::Flags::TEXT_NO_BREAKS);
      }
    }

    void SetCapitalization(uint32_t aOffset, uint32_t aLength,
                           bool* aCapitalize) final {
      MOZ_ASSERT(
          mTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_TRANSFORMED,
          "Text run should be transformed!");
      if (mTextRun->GetFlags2() &
          nsTextFrameUtils::Flags::TEXT_IS_TRANSFORMED) {
        nsTransformedTextRun* transformedTextRun =
            static_cast<nsTransformedTextRun*>(mTextRun.get());
        transformedTextRun->SetCapitalization(aOffset + mOffsetIntoTextRun,
                                              aLength, aCapitalize);
      }
    }

    void Finish(gfxMissingFontRecorder* aMFR) {
      MOZ_ASSERT(
          !(mTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_UNUSED_FLAGS),
          "Flag set that should never be set! (memory safety error?)");
      if (mTextRun->GetFlags2() &
          nsTextFrameUtils::Flags::TEXT_IS_TRANSFORMED) {
        nsTransformedTextRun* transformedTextRun =
            static_cast<nsTransformedTextRun*>(mTextRun.get());
        transformedTextRun->FinishSettingProperties(mDrawTarget, aMFR);
      }
      // The way nsTransformedTextRun is implemented, its glyph runs aren't
      // available until after nsTransformedTextRun::FinishSettingProperties()
      // is called. So that's why we defer checking for animated glyphs to here.
      CreateObserversForAnimatedGlyphs(mTextRun);
    }

    RefPtr<gfxTextRun> mTextRun;
    DrawTarget* mDrawTarget;
    uint32_t mOffsetIntoTextRun;
  };

 private:
  AutoTArray<MappedFlow, 10> mMappedFlows;
  AutoTArray<nsTextFrame*, 50> mLineBreakBeforeFrames;
  AutoTArray<UniquePtr<BreakSink>, 10> mBreakSinks;
  nsLineBreaker mLineBreaker;
  RefPtr<gfxTextRun> mCurrentFramesAllSameTextRun;
  DrawTarget* mDrawTarget;
  nsIFrame* mLineContainer;
  nsTextFrame* mLastFrame;
  // The common ancestor of the current frame and the previous leaf frame
  // on the line, or null if there was no previous leaf frame.
  nsIFrame* mCommonAncestorWithLastFrame;
  gfxMissingFontRecorder* mMissingFonts;
  // mMaxTextLength is an upper bound on the size of the text in all mapped
  // frames The value UINT32_MAX represents overflow; text will be discarded
  uint32_t mMaxTextLength;
  bool mDoubleByteText;
  bool mBidiEnabled;
  bool mStartOfLine;
  bool mSkipIncompleteTextRuns;
  bool mCanStopOnThisLine;
  nsTextFrame::TextRunType mWhichTextRun;
  uint8_t mNextRunContextInfo;
  uint8_t mCurrentRunContextInfo;
};

static nsIFrame* FindLineContainer(nsIFrame* aFrame) {
  while (aFrame && (aFrame->IsFrameOfType(nsIFrame::eLineParticipant) ||
                    aFrame->CanContinueTextRun())) {
    aFrame = aFrame->GetParent();
  }
  return aFrame;
}

static bool IsLineBreakingWhiteSpace(char16_t aChar) {
  // 0x0A (\n) is not handled as white-space by the line breaker, since
  // we break before it, if it isn't transformed to a normal space.
  // (If we treat it as normal white-space then we'd only break after it.)
  // However, it does induce a line break or is converted to a regular
  // space, and either way it can be used to bound the region of text
  // that needs to be analyzed for line breaking.
  return nsLineBreaker::IsSpace(aChar) || aChar == 0x0A;
}

static bool TextContainsLineBreakerWhiteSpace(const void* aText,
                                              uint32_t aLength,
                                              bool aIsDoubleByte) {
  if (aIsDoubleByte) {
    const char16_t* chars = static_cast<const char16_t*>(aText);
    for (uint32_t i = 0; i < aLength; ++i) {
      if (IsLineBreakingWhiteSpace(chars[i])) return true;
    }
    return false;
  } else {
    const uint8_t* chars = static_cast<const uint8_t*>(aText);
    for (uint32_t i = 0; i < aLength; ++i) {
      if (IsLineBreakingWhiteSpace(chars[i])) return true;
    }
    return false;
  }
}

static_assert(uint8_t(mozilla::StyleWhiteSpace::Normal) == 0,
              "Convention: StyleWhiteSpace::Normal should be 0");
static_assert(uint8_t(mozilla::StyleWhiteSpace::Pre) == 1,
              "Convention: StyleWhiteSpace::Pre should be 1");
static_assert(uint8_t(mozilla::StyleWhiteSpace::Nowrap) == 2,
              "Convention: StyleWhiteSpace::NoWrap should be 2");
static_assert(uint8_t(mozilla::StyleWhiteSpace::PreWrap) == 3,
              "Convention: StyleWhiteSpace::PreWrap should be 3");
static_assert(uint8_t(mozilla::StyleWhiteSpace::PreLine) == 4,
              "Convention: StyleWhiteSpace::PreLine should be 4");
static_assert(uint8_t(mozilla::StyleWhiteSpace::PreSpace) == 5,
              "Convention: StyleWhiteSpace::PreSpace should be 5");

static nsTextFrameUtils::CompressionMode GetCSSWhitespaceToCompressionMode(
    nsTextFrame* aFrame, const nsStyleText* aStyleText) {
  static const nsTextFrameUtils::CompressionMode sModes[] = {
      nsTextFrameUtils::COMPRESS_WHITESPACE_NEWLINE,      // normal
      nsTextFrameUtils::COMPRESS_NONE,                    // pre
      nsTextFrameUtils::COMPRESS_WHITESPACE_NEWLINE,      // nowrap
      nsTextFrameUtils::COMPRESS_NONE,                    // pre-wrap
      nsTextFrameUtils::COMPRESS_WHITESPACE,              // pre-line
      nsTextFrameUtils::COMPRESS_NONE_TRANSFORM_TO_SPACE  // -moz-pre-space
  };

  auto compression = sModes[uint8_t(aStyleText->mWhiteSpace)];
  if (compression == nsTextFrameUtils::COMPRESS_NONE &&
      !aStyleText->NewlineIsSignificant(aFrame)) {
    // If newline is set to be preserved, but then suppressed,
    // transform newline to space.
    compression = nsTextFrameUtils::COMPRESS_NONE_TRANSFORM_TO_SPACE;
  }
  return compression;
}

struct FrameTextTraversal {
  FrameTextTraversal()
      : mFrameToScan(nullptr),
        mOverflowFrameToScan(nullptr),
        mScanSiblings(false),
        mLineBreakerCanCrossFrameBoundary(false),
        mTextRunCanCrossFrameBoundary(false) {}

  // These fields identify which frames should be recursively scanned
  // The first normal frame to scan (or null, if no such frame should be
  // scanned)
  nsIFrame* mFrameToScan;
  // The first overflow frame to scan (or null, if no such frame should be
  // scanned)
  nsIFrame* mOverflowFrameToScan;
  // Whether to scan the siblings of
  // mFrameToDescendInto/mOverflowFrameToDescendInto
  bool mScanSiblings;

  // These identify the boundaries of the context required for
  // line breaking or textrun construction
  bool mLineBreakerCanCrossFrameBoundary;
  bool mTextRunCanCrossFrameBoundary;

  nsIFrame* NextFrameToScan() {
    nsIFrame* f;
    if (mFrameToScan) {
      f = mFrameToScan;
      mFrameToScan = mScanSiblings ? f->GetNextSibling() : nullptr;
    } else if (mOverflowFrameToScan) {
      f = mOverflowFrameToScan;
      mOverflowFrameToScan = mScanSiblings ? f->GetNextSibling() : nullptr;
    } else {
      f = nullptr;
    }
    return f;
  }
};

static FrameTextTraversal CanTextCrossFrameBoundary(nsIFrame* aFrame) {
  FrameTextTraversal result;

  bool continuesTextRun = aFrame->CanContinueTextRun();
  if (aFrame->IsPlaceholderFrame()) {
    // placeholders are "invisible", so a text run should be able to span
    // across one. But don't descend into the out-of-flow.
    result.mLineBreakerCanCrossFrameBoundary = true;
    if (continuesTextRun) {
      // ... Except for first-letter floats, which are really in-flow
      // from the point of view of capitalization etc, so we'd better
      // descend into them. But we actually need to break the textrun for
      // first-letter floats since things look bad if, say, we try to make a
      // ligature across the float boundary.
      result.mFrameToScan =
          (static_cast<nsPlaceholderFrame*>(aFrame))->GetOutOfFlowFrame();
    } else {
      result.mTextRunCanCrossFrameBoundary = true;
    }
  } else {
    if (continuesTextRun) {
      result.mFrameToScan = aFrame->PrincipalChildList().FirstChild();
      result.mOverflowFrameToScan =
          aFrame->GetChildList(nsIFrame::kOverflowList).FirstChild();
      NS_WARNING_ASSERTION(
          !result.mOverflowFrameToScan,
          "Scanning overflow inline frames is something we should avoid");
      result.mScanSiblings = true;
      result.mTextRunCanCrossFrameBoundary = true;
      result.mLineBreakerCanCrossFrameBoundary = true;
    } else {
      MOZ_ASSERT(!aFrame->IsRubyTextContainerFrame(),
                 "Shouldn't call this method for ruby text container");
    }
  }
  return result;
}

BuildTextRunsScanner::FindBoundaryResult BuildTextRunsScanner::FindBoundaries(
    nsIFrame* aFrame, FindBoundaryState* aState) {
  LayoutFrameType frameType = aFrame->Type();
  if (frameType == LayoutFrameType::RubyTextContainer) {
    // Don't stop a text run for ruby text container. We want ruby text
    // containers to be skipped, but continue the text run across them.
    return FB_CONTINUE;
  }

  nsTextFrame* textFrame = frameType == LayoutFrameType::Text
                               ? static_cast<nsTextFrame*>(aFrame)
                               : nullptr;
  if (textFrame) {
    if (aState->mLastTextFrame &&
        textFrame != aState->mLastTextFrame->GetNextInFlow() &&
        !ContinueTextRunAcrossFrames(aState->mLastTextFrame, textFrame)) {
      aState->mSeenTextRunBoundaryOnThisLine = true;
      if (aState->mSeenSpaceForLineBreakingOnThisLine)
        return FB_FOUND_VALID_TEXTRUN_BOUNDARY;
    }
    if (!aState->mFirstTextFrame) {
      aState->mFirstTextFrame = textFrame;
    }
    aState->mLastTextFrame = textFrame;
  }

  if (aFrame == aState->mStopAtFrame) return FB_STOPPED_AT_STOP_FRAME;

  if (textFrame) {
    if (aState->mSeenSpaceForLineBreakingOnThisLine) {
      return FB_CONTINUE;
    }
    const nsTextFragment* frag = textFrame->GetContent()->GetText();
    uint32_t start = textFrame->GetContentOffset();
    uint32_t length = textFrame->GetContentLength();
    const void* text;
    if (frag->Is2b()) {
      // It is possible that we may end up removing all whitespace in
      // a piece of text because of The White Space Processing Rules,
      // so we need to transform it before we can check existence of
      // such whitespaces.
      aState->mBuffer.EnsureLengthAtLeast(length);
      nsTextFrameUtils::CompressionMode compression =
          GetCSSWhitespaceToCompressionMode(textFrame, textFrame->StyleText());
      uint8_t incomingFlags = 0;
      gfxSkipChars skipChars;
      nsTextFrameUtils::Flags analysisFlags;
      char16_t* bufStart = aState->mBuffer.Elements();
      char16_t* bufEnd = nsTextFrameUtils::TransformText(
          frag->Get2b() + start, length, bufStart, compression, &incomingFlags,
          &skipChars, &analysisFlags);
      text = bufStart;
      length = bufEnd - bufStart;
    } else {
      // If the text only contains ASCII characters, it is currently
      // impossible that TransformText would remove all whitespaces,
      // and thus the check below should return the same result for
      // transformed text and original text. So we don't need to try
      // transforming it here.
      text = static_cast<const void*>(frag->Get1b() + start);
    }
    if (TextContainsLineBreakerWhiteSpace(text, length, frag->Is2b())) {
      aState->mSeenSpaceForLineBreakingOnThisLine = true;
      if (aState->mSeenTextRunBoundaryOnLaterLine) {
        return FB_FOUND_VALID_TEXTRUN_BOUNDARY;
      }
    }
    return FB_CONTINUE;
  }

  FrameTextTraversal traversal = CanTextCrossFrameBoundary(aFrame);
  if (!traversal.mTextRunCanCrossFrameBoundary) {
    aState->mSeenTextRunBoundaryOnThisLine = true;
    if (aState->mSeenSpaceForLineBreakingOnThisLine)
      return FB_FOUND_VALID_TEXTRUN_BOUNDARY;
  }

  for (nsIFrame* f = traversal.NextFrameToScan(); f;
       f = traversal.NextFrameToScan()) {
    FindBoundaryResult result = FindBoundaries(f, aState);
    if (result != FB_CONTINUE) return result;
  }

  if (!traversal.mTextRunCanCrossFrameBoundary) {
    aState->mSeenTextRunBoundaryOnThisLine = true;
    if (aState->mSeenSpaceForLineBreakingOnThisLine)
      return FB_FOUND_VALID_TEXTRUN_BOUNDARY;
  }

  return FB_CONTINUE;
}

// build text runs for the 200 lines following aForFrame, and stop after that
// when we get a chance.
#define NUM_LINES_TO_BUILD_TEXT_RUNS 200

/**
 * General routine for building text runs. This is hairy because of the need
 * to build text runs that span content nodes.
 *
 * @param aContext The gfxContext we're using to construct this text run.
 * @param aForFrame The nsTextFrame for which we're building this text run.
 * @param aLineContainer the line container containing aForFrame; if null,
 *        we'll walk the ancestors to find it.  It's required to be non-null
 *        when aForFrameLine is non-null.
 * @param aForFrameLine the line containing aForFrame; if null, we'll figure
 *        out the line (slowly)
 * @param aWhichTextRun The type of text run we want to build. If font inflation
 *        is enabled, this will be eInflated, otherwise it's eNotInflated.
 */
static void BuildTextRuns(DrawTarget* aDrawTarget, nsTextFrame* aForFrame,
                          nsIFrame* aLineContainer,
                          const nsLineList::iterator* aForFrameLine,
                          nsTextFrame::TextRunType aWhichTextRun) {
  MOZ_ASSERT(aForFrame, "for no frame?");
  NS_ASSERTION(!aForFrameLine || aLineContainer, "line but no line container");

  nsIFrame* lineContainerChild = aForFrame;
  if (!aLineContainer) {
    if (aForFrame->IsFloatingFirstLetterChild()) {
      lineContainerChild = aForFrame->GetParent()->GetPlaceholderFrame();
    }
    aLineContainer = FindLineContainer(lineContainerChild);
  } else {
    NS_ASSERTION(
        (aLineContainer == FindLineContainer(aForFrame) ||
         (aLineContainer->IsLetterFrame() && aLineContainer->IsFloating())),
        "Wrong line container hint");
  }

  if (aForFrame->HasAnyStateBits(TEXT_IS_IN_TOKEN_MATHML)) {
    aLineContainer->AddStateBits(TEXT_IS_IN_TOKEN_MATHML);
    if (aForFrame->HasAnyStateBits(NS_FRAME_IS_IN_SINGLE_CHAR_MI)) {
      aLineContainer->AddStateBits(NS_FRAME_IS_IN_SINGLE_CHAR_MI);
    }
  }
  if (aForFrame->HasAnyStateBits(NS_FRAME_MATHML_SCRIPT_DESCENDANT)) {
    aLineContainer->AddStateBits(NS_FRAME_MATHML_SCRIPT_DESCENDANT);
  }

  nsPresContext* presContext = aLineContainer->PresContext();
  BuildTextRunsScanner scanner(presContext, aDrawTarget, aLineContainer,
                               aWhichTextRun);

  nsBlockFrame* block = nsLayoutUtils::GetAsBlock(aLineContainer);

  if (!block) {
    nsIFrame* textRunContainer = aLineContainer;
    if (aLineContainer->IsRubyTextContainerFrame()) {
      textRunContainer = aForFrame;
      while (textRunContainer && !textRunContainer->IsRubyTextFrame()) {
        textRunContainer = textRunContainer->GetParent();
      }
      MOZ_ASSERT(textRunContainer &&
                 textRunContainer->GetParent() == aLineContainer);
    } else {
      NS_ASSERTION(
          !aLineContainer->GetPrevInFlow() && !aLineContainer->GetNextInFlow(),
          "Breakable non-block line containers other than "
          "ruby text container is not supported");
    }
    // Just loop through all the children of the linecontainer ... it's really
    // just one line
    scanner.SetAtStartOfLine();
    scanner.SetCommonAncestorWithLastFrame(nullptr);
    for (nsIFrame* child : textRunContainer->PrincipalChildList()) {
      scanner.ScanFrame(child);
    }
    // Set mStartOfLine so FlushFrames knows its textrun ends a line
    scanner.SetAtStartOfLine();
    scanner.FlushFrames(true, false);
    return;
  }

  // Find the line containing 'lineContainerChild'.

  bool isValid = true;
  nsBlockInFlowLineIterator backIterator(block, &isValid);
  if (aForFrameLine) {
    backIterator = nsBlockInFlowLineIterator(block, *aForFrameLine);
  } else {
    backIterator =
        nsBlockInFlowLineIterator(block, lineContainerChild, &isValid);
    NS_ASSERTION(isValid, "aForFrame not found in block, someone lied to us");
    NS_ASSERTION(backIterator.GetContainer() == block,
                 "Someone lied to us about the block");
  }
  nsBlockFrame::LineIterator startLine = backIterator.GetLine();

  // Find a line where we can start building text runs. We choose the last line
  // where:
  // -- there is a textrun boundary between the start of the line and the
  // start of aForFrame
  // -- there is a space between the start of the line and the textrun boundary
  // (this is so we can be sure the line breaks will be set properly
  // on the textruns we construct).
  // The possibly-partial text runs up to and including the first space
  // are not reconstructed. We construct partial text runs for that text ---
  // for the sake of simplifying the code and feeding the linebreaker ---
  // but we discard them instead of assigning them to frames.
  // This is a little awkward because we traverse lines in the reverse direction
  // but we traverse the frames in each line in the forward direction.
  nsBlockInFlowLineIterator forwardIterator = backIterator;
  nsIFrame* stopAtFrame = lineContainerChild;
  nsTextFrame* nextLineFirstTextFrame = nullptr;
  AutoTArray<char16_t, BIG_TEXT_NODE_SIZE> buffer;
  bool seenTextRunBoundaryOnLaterLine = false;
  bool mayBeginInTextRun = true;
  while (true) {
    forwardIterator = backIterator;
    nsBlockFrame::LineIterator line = backIterator.GetLine();
    if (!backIterator.Prev() || backIterator.GetLine()->IsBlock()) {
      mayBeginInTextRun = false;
      break;
    }

    BuildTextRunsScanner::FindBoundaryState state = {
        stopAtFrame, nullptr, nullptr, bool(seenTextRunBoundaryOnLaterLine),
        false,       false,   buffer};
    nsIFrame* child = line->mFirstChild;
    bool foundBoundary = false;
    for (int32_t i = line->GetChildCount() - 1; i >= 0; --i) {
      BuildTextRunsScanner::FindBoundaryResult result =
          scanner.FindBoundaries(child, &state);
      if (result == BuildTextRunsScanner::FB_FOUND_VALID_TEXTRUN_BOUNDARY) {
        foundBoundary = true;
        break;
      } else if (result == BuildTextRunsScanner::FB_STOPPED_AT_STOP_FRAME) {
        break;
      }
      child = child->GetNextSibling();
    }
    if (foundBoundary) break;
    if (!stopAtFrame && state.mLastTextFrame && nextLineFirstTextFrame &&
        !scanner.ContinueTextRunAcrossFrames(state.mLastTextFrame,
                                             nextLineFirstTextFrame)) {
      // Found a usable textrun boundary at the end of the line
      if (state.mSeenSpaceForLineBreakingOnThisLine) break;
      seenTextRunBoundaryOnLaterLine = true;
    } else if (state.mSeenTextRunBoundaryOnThisLine) {
      seenTextRunBoundaryOnLaterLine = true;
    }
    stopAtFrame = nullptr;
    if (state.mFirstTextFrame) {
      nextLineFirstTextFrame = state.mFirstTextFrame;
    }
  }
  scanner.SetSkipIncompleteTextRuns(mayBeginInTextRun);

  // Now iterate over all text frames starting from the current line.
  // First-in-flow text frames will be accumulated into textRunFrames as we go.
  // When a text run boundary is required we flush textRunFrames ((re)building
  // their gfxTextRuns as necessary).
  bool seenStartLine = false;
  uint32_t linesAfterStartLine = 0;
  do {
    nsBlockFrame::LineIterator line = forwardIterator.GetLine();
    if (line->IsBlock()) break;
    line->SetInvalidateTextRuns(false);
    scanner.SetAtStartOfLine();
    scanner.SetCommonAncestorWithLastFrame(nullptr);
    nsIFrame* child = line->mFirstChild;
    for (int32_t i = line->GetChildCount() - 1; i >= 0; --i) {
      scanner.ScanFrame(child);
      child = child->GetNextSibling();
    }
    if (line.get() == startLine.get()) {
      seenStartLine = true;
    }
    if (seenStartLine) {
      ++linesAfterStartLine;
      if (linesAfterStartLine >= NUM_LINES_TO_BUILD_TEXT_RUNS &&
          scanner.CanStopOnThisLine()) {
        // Don't flush frames; we may be in the middle of a textrun
        // that we can't end here. That's OK, we just won't build it.
        // Note that we must already have finished the textrun for aForFrame,
        // because we've seen the end of a textrun in a line after the line
        // containing aForFrame.
        scanner.FlushLineBreaks(nullptr);
        // This flushes out mMappedFlows and mLineBreakBeforeFrames, which
        // silences assertions in the scanner destructor.
        scanner.ResetRunInfo();
        return;
      }
    }
  } while (forwardIterator.Next());

  // Set mStartOfLine so FlushFrames knows its textrun ends a line
  scanner.SetAtStartOfLine();
  scanner.FlushFrames(true, false);
}

static char16_t* ExpandBuffer(char16_t* aDest, uint8_t* aSrc, uint32_t aCount) {
  while (aCount) {
    *aDest = *aSrc;
    ++aDest;
    ++aSrc;
    --aCount;
  }
  return aDest;
}

bool BuildTextRunsScanner::IsTextRunValidForMappedFlows(
    const gfxTextRun* aTextRun) {
  if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    return mMappedFlows.Length() == 1 &&
           mMappedFlows[0].mStartFrame == GetFrameForSimpleFlow(aTextRun) &&
           mMappedFlows[0].mEndFrame == nullptr;
  }

  auto userData = static_cast<TextRunUserData*>(aTextRun->GetUserData());
  TextRunMappedFlow* userMappedFlows = GetMappedFlows(aTextRun);
  if (userData->mMappedFlowCount != mMappedFlows.Length()) return false;
  for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
    if (userMappedFlows[i].mStartFrame != mMappedFlows[i].mStartFrame ||
        int32_t(userMappedFlows[i].mContentLength) !=
            mMappedFlows[i].GetContentEnd() -
                mMappedFlows[i].mStartFrame->GetContentOffset())
      return false;
  }
  return true;
}

/**
 * This gets called when we need to make a text run for the current list of
 * frames.
 */
void BuildTextRunsScanner::FlushFrames(bool aFlushLineBreaks,
                                       bool aSuppressTrailingBreak) {
  RefPtr<gfxTextRun> textRun;
  if (!mMappedFlows.IsEmpty()) {
    if (!mSkipIncompleteTextRuns && mCurrentFramesAllSameTextRun &&
        !!(mCurrentFramesAllSameTextRun->GetFlags2() &
           nsTextFrameUtils::Flags::TEXT_INCOMING_WHITESPACE) ==
            !!(mCurrentRunContextInfo &
               nsTextFrameUtils::INCOMING_WHITESPACE) &&
        !!(mCurrentFramesAllSameTextRun->GetFlags() &
           gfx::ShapedTextFlags::TEXT_INCOMING_ARABICCHAR) ==
            !!(mCurrentRunContextInfo &
               nsTextFrameUtils::INCOMING_ARABICCHAR) &&
        IsTextRunValidForMappedFlows(mCurrentFramesAllSameTextRun)) {
      // Optimization: We do not need to (re)build the textrun.
      textRun = mCurrentFramesAllSameTextRun;

      // Feed this run's text into the linebreaker to provide context.
      if (!SetupLineBreakerContext(textRun)) {
        return;
      }

      // Update mNextRunContextInfo appropriately
      mNextRunContextInfo = nsTextFrameUtils::INCOMING_NONE;
      if (textRun->GetFlags2() &
          nsTextFrameUtils::Flags::TEXT_TRAILING_WHITESPACE) {
        mNextRunContextInfo |= nsTextFrameUtils::INCOMING_WHITESPACE;
      }
      if (textRun->GetFlags() &
          gfx::ShapedTextFlags::TEXT_TRAILING_ARABICCHAR) {
        mNextRunContextInfo |= nsTextFrameUtils::INCOMING_ARABICCHAR;
      }
    } else {
      AutoTArray<uint8_t, BIG_TEXT_NODE_SIZE> buffer;
      uint32_t bufferSize = mMaxTextLength * (mDoubleByteText ? 2 : 1);
      if (bufferSize < mMaxTextLength || bufferSize == UINT32_MAX ||
          !buffer.AppendElements(bufferSize, fallible)) {
        return;
      }
      textRun = BuildTextRunForFrames(buffer.Elements());
    }
  }

  if (aFlushLineBreaks) {
    FlushLineBreaks(aSuppressTrailingBreak ? nullptr : textRun.get());
  }

  mCanStopOnThisLine = true;
  ResetRunInfo();
}

void BuildTextRunsScanner::FlushLineBreaks(gfxTextRun* aTrailingTextRun) {
  bool trailingLineBreak;
  nsresult rv = mLineBreaker.Reset(&trailingLineBreak);
  // textRun may be null for various reasons, including because we constructed
  // a partial textrun just to get the linebreaker and other state set up
  // to build the next textrun.
  if (NS_SUCCEEDED(rv) && trailingLineBreak && aTrailingTextRun) {
    aTrailingTextRun->SetFlagBits(
        nsTextFrameUtils::Flags::TEXT_HAS_TRAILING_BREAK);
  }

  for (uint32_t i = 0; i < mBreakSinks.Length(); ++i) {
    // TODO cause frames associated with the textrun to be reflowed, if they
    // aren't being reflowed already!
    mBreakSinks[i]->Finish(mMissingFonts);
  }
  mBreakSinks.Clear();
}

void BuildTextRunsScanner::AccumulateRunInfo(nsTextFrame* aFrame) {
  if (mMaxTextLength != UINT32_MAX) {
    NS_ASSERTION(mMaxTextLength < UINT32_MAX - aFrame->GetContentLength(),
                 "integer overflow");
    if (mMaxTextLength >= UINT32_MAX - aFrame->GetContentLength()) {
      mMaxTextLength = UINT32_MAX;
    } else {
      mMaxTextLength += aFrame->GetContentLength();
    }
  }
  mDoubleByteText |= aFrame->GetContent()->GetText()->Is2b();
  mLastFrame = aFrame;
  mCommonAncestorWithLastFrame = aFrame->GetParent();

  MappedFlow* mappedFlow = &mMappedFlows[mMappedFlows.Length() - 1];
  NS_ASSERTION(mappedFlow->mStartFrame == aFrame ||
                   mappedFlow->GetContentEnd() == aFrame->GetContentOffset(),
               "Overlapping or discontiguous frames => BAD");
  mappedFlow->mEndFrame = aFrame->GetNextContinuation();
  if (mCurrentFramesAllSameTextRun != aFrame->GetTextRun(mWhichTextRun)) {
    mCurrentFramesAllSameTextRun = nullptr;
  }

  if (mStartOfLine) {
    mLineBreakBeforeFrames.AppendElement(aFrame);
    mStartOfLine = false;
  }
}

static bool HasTerminalNewline(const nsTextFrame* aFrame) {
  if (aFrame->GetContentLength() == 0) return false;
  const nsTextFragment* frag = aFrame->GetContent()->GetText();
  return frag->CharAt(aFrame->GetContentEnd() - 1) == '\n';
}

static gfxFont::Metrics GetFirstFontMetrics(gfxFontGroup* aFontGroup,
                                            bool aVerticalMetrics) {
  if (!aFontGroup) return gfxFont::Metrics();
  gfxFont* font = aFontGroup->GetFirstValidFont();
  return font->GetMetrics(aVerticalMetrics ? gfxFont::eVertical
                                           : gfxFont::eHorizontal);
}

static gfxFloat GetSpaceWidthAppUnits(const gfxTextRun* aTextRun) {
  // Round the space width when converting to appunits the same way textruns
  // do.
  gfxFloat spaceWidthAppUnits =
      NS_round(GetFirstFontMetrics(aTextRun->GetFontGroup(),
                                   aTextRun->UseCenterBaseline())
                   .spaceWidth *
               aTextRun->GetAppUnitsPerDevUnit());

  return spaceWidthAppUnits;
}

static gfxFloat GetMinTabAdvanceAppUnits(const gfxTextRun* aTextRun) {
  gfxFloat chWidthAppUnits = NS_round(
      GetFirstFontMetrics(aTextRun->GetFontGroup(), aTextRun->IsVertical())
          .zeroOrAveCharWidth *
      aTextRun->GetAppUnitsPerDevUnit());
  return 0.5 * chWidthAppUnits;
}

static nscoord LetterSpacing(nsIFrame* aFrame,
                             const nsStyleText* aStyleText = nullptr) {
  if (nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    return 0;
  }
  if (!aStyleText) {
    aStyleText = aFrame->StyleText();
  }

  const nsStyleCoord& coord = aStyleText->mLetterSpacing;
  if (eStyleUnit_Coord == coord.GetUnit()) {
    return coord.GetCoordValue();
  }
  return 0;
}

// This function converts non-coord values (e.g. percentages) to nscoord.
static nscoord WordSpacing(nsIFrame* aFrame, const gfxTextRun* aTextRun,
                           const nsStyleText* aStyleText = nullptr) {
  if (nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    return 0;
  }
  if (!aStyleText) {
    aStyleText = aFrame->StyleText();
  }

  const nsStyleCoord& coord = aStyleText->mWordSpacing;
  if (coord.IsCoordPercentCalcUnit()) {
    nscoord pctBasis = coord.HasPercent() ? GetSpaceWidthAppUnits(aTextRun) : 0;
    return coord.ComputeCoordPercentCalc(pctBasis);
  }
  return 0;
}

// Returns gfxTextRunFactory::TEXT_ENABLE_SPACING if non-standard
// letter-spacing or word-spacing is present.
static gfx::ShapedTextFlags GetSpacingFlags(
    nsIFrame* aFrame, const nsStyleText* aStyleText = nullptr) {
  if (nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    return gfx::ShapedTextFlags();
  }

  const nsStyleText* styleText = aFrame->StyleText();
  const nsStyleCoord& ls = styleText->mLetterSpacing;
  const nsStyleCoord& ws = styleText->mWordSpacing;

  // It's possible to have a calc() value that computes to zero but for which
  // IsDefinitelyZero() is false, in which case we'll return
  // TEXT_ENABLE_SPACING unnecessarily. That's ok because such cases are likely
  // to be rare, and avoiding TEXT_ENABLE_SPACING is just an optimization.
  bool nonStandardSpacing =
      (eStyleUnit_Coord == ls.GetUnit() && ls.GetCoordValue() != 0) ||
      (eStyleUnit_Coord == ws.GetUnit() && ws.GetCoordValue() != 0) ||
      (eStyleUnit_Percent == ws.GetUnit() && ws.GetPercentValue() != 0) ||
      (eStyleUnit_Calc == ws.GetUnit() &&
       !ws.GetCalcValue()->IsDefinitelyZero());

  return nonStandardSpacing ? gfx::ShapedTextFlags::TEXT_ENABLE_SPACING
                            : gfx::ShapedTextFlags();
}

bool BuildTextRunsScanner::ContinueTextRunAcrossFrames(nsTextFrame* aFrame1,
                                                       nsTextFrame* aFrame2) {
  // We don't need to check font size inflation, since
  // |FindLineContainer| above (via |nsIFrame::CanContinueTextRun|)
  // ensures that text runs never cross block boundaries.  This means
  // that the font size inflation on all text frames in the text run is
  // already guaranteed to be the same as each other (and for the line
  // container).
  if (mBidiEnabled) {
    FrameBidiData data1 = aFrame1->GetBidiData();
    FrameBidiData data2 = aFrame2->GetBidiData();
    if (data1.embeddingLevel != data2.embeddingLevel ||
        data2.precedingControl != kBidiLevelNone) {
      return false;
    }
  }

  ComputedStyle* sc1 = aFrame1->Style();
  ComputedStyle* sc2 = aFrame2->Style();

  // Any difference in writing-mode/directionality inhibits shaping across
  // the boundary.
  WritingMode wm(sc1);
  if (wm != WritingMode(sc2)) {
    return false;
  }

  const nsStyleText* textStyle1 = sc1->StyleText();
  // If the first frame ends in a preformatted newline, then we end the textrun
  // here. This avoids creating giant textruns for an entire plain text file.
  // Note that we create a single text frame for a preformatted text node,
  // even if it has newlines in it, so typically we won't see trailing newlines
  // until after reflow has broken up the frame into one (or more) frames per
  // line. That's OK though.
  if (textStyle1->NewlineIsSignificant(aFrame1) &&
      HasTerminalNewline(aFrame1)) {
    return false;
  }

  if (aFrame1->GetParent()->GetContent() !=
      aFrame2->GetParent()->GetContent()) {
    // Does aFrame, or any ancestor between it and aAncestor, have a property
    // that should inhibit cross-element-boundary shaping on aSide?
    auto PreventCrossBoundaryShaping = [](const nsIFrame* aFrame,
                                          const nsIFrame* aAncestor,
                                          Side aSide) {
      while (aFrame != aAncestor) {
        ComputedStyle* ctx = aFrame->Style();
        // According to https://drafts.csswg.org/css-text/#boundary-shaping:
        //
        // Text shaping must be broken at inline box boundaries when any of the
        // following are true for any box whose boundary separates the two
        // typographic character units:
        //
        // 1. Any of margin/border/padding separating the two typographic
        //    character units in the inline axis is non-zero.
        const nsStyleCoord& margin = ctx->StyleMargin()->mMargin.Get(aSide);
        if (!margin.ConvertsToLength() || margin.ToLength() != 0) {
          return true;
        }
        const nsStyleCoord& padding = ctx->StylePadding()->mPadding.Get(aSide);
        if (!padding.ConvertsToLength() || padding.ToLength() != 0) {
          return true;
        }
        if (ctx->StyleBorder()->GetComputedBorderWidth(aSide) != 0) {
          return true;
        }

        // 2. vertical-align is not baseline.
        const nsStyleCoord& coord = ctx->StyleDisplay()->mVerticalAlign;
        if (coord.GetUnit() != eStyleUnit_Enumerated ||
            coord.GetIntValue() != NS_STYLE_VERTICAL_ALIGN_BASELINE) {
          return true;
        }

        // 3. The boundary is a bidi isolation boundary.
        const uint8_t unicodeBidi = ctx->StyleTextReset()->mUnicodeBidi;
        if (unicodeBidi == NS_STYLE_UNICODE_BIDI_ISOLATE ||
            unicodeBidi == NS_STYLE_UNICODE_BIDI_ISOLATE_OVERRIDE) {
          return true;
        }

        aFrame = aFrame->GetParent();
      }
      return false;
    };

    const nsIFrame* ancestor =
      nsLayoutUtils::FindNearestCommonAncestorFrame(aFrame1, aFrame2);
    MOZ_ASSERT(ancestor);

    // Map inline-end and inline-start to physical sides for checking presence
    // of non-zero margin/border/padding.
    Side side1 = wm.PhysicalSide(eLogicalSideIEnd);
    Side side2 = wm.PhysicalSide(eLogicalSideIStart);
    // If the frames have an embedding level that is opposite to the writing
    // mode, we need to swap which sides we're checking.
    if (IS_LEVEL_RTL(aFrame1->GetEmbeddingLevel()) == wm.IsBidiLTR()) {
      Swap(side1, side2);
    }

    if (PreventCrossBoundaryShaping(aFrame1, ancestor, side1) ||
        PreventCrossBoundaryShaping(aFrame2, ancestor, side2)) {
      return false;
    }
  }

  if (aFrame1->GetContent() == aFrame2->GetContent() &&
      aFrame1->GetNextInFlow() != aFrame2) {
    // aFrame2 must be a non-fluid continuation of aFrame1. This can happen
    // sometimes when the unicode-bidi property is used; the bidi resolver
    // breaks text into different frames even though the text has the same
    // direction. We can't allow these two frames to share the same textrun
    // because that would violate our invariant that two flows in the same
    // textrun have different content elements.
    return false;
  }

  if (sc1 == sc2) {
    return true;
  }

  const nsStyleText* textStyle2 = sc2->StyleText();
  if (sc1 == sc2) return true;

  nsPresContext* pc = aFrame1->PresContext();
  MOZ_ASSERT(pc == aFrame2->PresContext());

  const nsStyleFont* fontStyle1 = sc1->StyleFont();
  const nsStyleFont* fontStyle2 = sc2->StyleFont();
  nscoord letterSpacing1 = LetterSpacing(aFrame1);
  nscoord letterSpacing2 = LetterSpacing(aFrame2);
  return fontStyle1->mFont == fontStyle2->mFont &&
         fontStyle1->mLanguage == fontStyle2->mLanguage &&
         textStyle1->mTextTransform == textStyle2->mTextTransform &&
         nsLayoutUtils::GetTextRunFlagsForStyle(sc1, pc, fontStyle1, textStyle1,
                                                letterSpacing1) ==
             nsLayoutUtils::GetTextRunFlagsForStyle(sc2, pc, fontStyle2,
                                                    textStyle2, letterSpacing2);
}

void BuildTextRunsScanner::ScanFrame(nsIFrame* aFrame) {
  LayoutFrameType frameType = aFrame->Type();
  if (frameType == LayoutFrameType::RubyTextContainer) {
    // Don't include any ruby text container into the text run.
    return;
  }

  // First check if we can extend the current mapped frame block. This is
  // common.
  if (mMappedFlows.Length() > 0) {
    MappedFlow* mappedFlow = &mMappedFlows[mMappedFlows.Length() - 1];
    if (mappedFlow->mEndFrame == aFrame &&
        (aFrame->GetStateBits() & NS_FRAME_IS_FLUID_CONTINUATION)) {
      NS_ASSERTION(frameType == LayoutFrameType::Text,
                   "Flow-sibling of a text frame is not a text frame?");

      // Don't do this optimization if mLastFrame has a terminal newline...
      // it's quite likely preformatted and we might want to end the textrun
      // here. This is almost always true:
      if (mLastFrame->Style() == aFrame->Style() &&
          !HasTerminalNewline(mLastFrame)) {
        AccumulateRunInfo(static_cast<nsTextFrame*>(aFrame));
        return;
      }
    }
  }

  // Now see if we can add a new set of frames to the current textrun
  if (frameType == LayoutFrameType::Text) {
    nsTextFrame* frame = static_cast<nsTextFrame*>(aFrame);

    if (mLastFrame) {
      if (!ContinueTextRunAcrossFrames(mLastFrame, frame)) {
        FlushFrames(false, false);
      } else {
        if (mLastFrame->GetContent() == frame->GetContent()) {
          AccumulateRunInfo(frame);
          return;
        }
      }
    }

    MappedFlow* mappedFlow = mMappedFlows.AppendElement();
    if (!mappedFlow) return;

    mappedFlow->mStartFrame = frame;
    mappedFlow->mAncestorControllingInitialBreak = mCommonAncestorWithLastFrame;

    AccumulateRunInfo(frame);
    if (mMappedFlows.Length() == 1) {
      mCurrentFramesAllSameTextRun = frame->GetTextRun(mWhichTextRun);
      mCurrentRunContextInfo = mNextRunContextInfo;
    }
    return;
  }

  FrameTextTraversal traversal = CanTextCrossFrameBoundary(aFrame);
  bool isBR = frameType == LayoutFrameType::Br;
  if (!traversal.mLineBreakerCanCrossFrameBoundary) {
    // BR frames are special. We do not need or want to record a break
    // opportunity before a BR frame.
    FlushFrames(true, isBR);
    mCommonAncestorWithLastFrame = aFrame;
    mNextRunContextInfo &= ~nsTextFrameUtils::INCOMING_WHITESPACE;
    mStartOfLine = false;
  } else if (!traversal.mTextRunCanCrossFrameBoundary) {
    FlushFrames(false, false);
  }

  for (nsIFrame* f = traversal.NextFrameToScan(); f;
       f = traversal.NextFrameToScan()) {
    ScanFrame(f);
  }

  if (!traversal.mLineBreakerCanCrossFrameBoundary) {
    // Really if we're a BR frame this is unnecessary since descendInto will be
    // false. In fact this whole "if" statement should move into the
    // descendInto.
    FlushFrames(true, isBR);
    mCommonAncestorWithLastFrame = aFrame;
    mNextRunContextInfo &= ~nsTextFrameUtils::INCOMING_WHITESPACE;
  } else if (!traversal.mTextRunCanCrossFrameBoundary) {
    FlushFrames(false, false);
  }

  LiftCommonAncestorWithLastFrameToParent(aFrame->GetParent());
}

nsTextFrame* BuildTextRunsScanner::GetNextBreakBeforeFrame(uint32_t* aIndex) {
  uint32_t index = *aIndex;
  if (index >= mLineBreakBeforeFrames.Length()) return nullptr;
  *aIndex = index + 1;
  return static_cast<nsTextFrame*>(mLineBreakBeforeFrames.ElementAt(index));
}

static gfxFontGroup* GetFontGroupForFrame(
    const nsIFrame* aFrame, float aFontSizeInflation,
    nsFontMetrics** aOutFontMetrics = nullptr) {
  RefPtr<nsFontMetrics> metrics =
      nsLayoutUtils::GetFontMetricsForFrame(aFrame, aFontSizeInflation);
  gfxFontGroup* fontGroup = metrics->GetThebesFontGroup();

  // Populate outparam before we return:
  if (aOutFontMetrics) {
    metrics.forget(aOutFontMetrics);
  }
  // XXX this is a bit bogus, we're releasing 'metrics' so the
  // returned font-group might actually be torn down, although because
  // of the way the device context caches font metrics, this seems to
  // not actually happen. But we should fix this.
  return fontGroup;
}

static gfxFontGroup* GetInflatedFontGroupForFrame(nsTextFrame* aFrame) {
  gfxTextRun* textRun = aFrame->GetTextRun(nsTextFrame::eInflated);
  if (textRun) {
    return textRun->GetFontGroup();
  }
  if (!aFrame->InflatedFontMetrics()) {
    float inflation = nsLayoutUtils::FontSizeInflationFor(aFrame);
    RefPtr<nsFontMetrics> metrics =
        nsLayoutUtils::GetFontMetricsForFrame(aFrame, inflation);
    aFrame->SetInflatedFontMetrics(metrics);
  }
  return aFrame->InflatedFontMetrics()->GetThebesFontGroup();
}

static already_AddRefed<DrawTarget> CreateReferenceDrawTarget(
    const nsTextFrame* aTextFrame) {
  RefPtr<gfxContext> ctx =
      aTextFrame->PresShell()->CreateReferenceRenderingContext();
  RefPtr<DrawTarget> dt = ctx->GetDrawTarget();
  return dt.forget();
}

static already_AddRefed<gfxTextRun> GetHyphenTextRun(const gfxTextRun* aTextRun,
                                                     DrawTarget* aDrawTarget,
                                                     nsTextFrame* aTextFrame) {
  RefPtr<DrawTarget> dt = aDrawTarget;
  if (!dt) {
    dt = CreateReferenceDrawTarget(aTextFrame);
    if (!dt) {
      return nullptr;
    }
  }

  return aTextRun->GetFontGroup()->MakeHyphenTextRun(
      dt, aTextRun->GetAppUnitsPerDevUnit());
}

already_AddRefed<gfxTextRun> BuildTextRunsScanner::BuildTextRunForFrames(
    void* aTextBuffer) {
  gfxSkipChars skipChars;

  const void* textPtr = aTextBuffer;
  bool anyTextTransformStyle = false;
  bool anyMathMLStyling = false;
  bool anyTextEmphasis = false;
  uint8_t sstyScriptLevel = 0;
  uint32_t mathFlags = 0;
  gfx::ShapedTextFlags flags = gfx::ShapedTextFlags();
  nsTextFrameUtils::Flags flags2 = nsTextFrameUtils::Flags::TEXT_NO_BREAKS;

  if (mCurrentRunContextInfo & nsTextFrameUtils::INCOMING_WHITESPACE) {
    flags2 |= nsTextFrameUtils::Flags::TEXT_INCOMING_WHITESPACE;
  }
  if (mCurrentRunContextInfo & nsTextFrameUtils::INCOMING_ARABICCHAR) {
    flags |= gfx::ShapedTextFlags::TEXT_INCOMING_ARABICCHAR;
  }

  AutoTArray<int32_t, 50> textBreakPoints;
  TextRunUserData dummyData;
  TextRunMappedFlow dummyMappedFlow;
  TextRunMappedFlow* userMappedFlows;
  TextRunUserData* userData;
  TextRunUserData* userDataToDestroy;
  // If the situation is particularly simple (and common) we don't need to
  // allocate userData.
  if (mMappedFlows.Length() == 1 && !mMappedFlows[0].mEndFrame &&
      mMappedFlows[0].mStartFrame->GetContentOffset() == 0) {
    userData = &dummyData;
    userMappedFlows = &dummyMappedFlow;
    userDataToDestroy = nullptr;
    dummyData.mMappedFlowCount = mMappedFlows.Length();
    dummyData.mLastFlowIndex = 0;
  } else {
    userData = CreateUserData(mMappedFlows.Length());
    userMappedFlows = reinterpret_cast<TextRunMappedFlow*>(userData + 1);
    userDataToDestroy = userData;
  }

  uint32_t currentTransformedTextOffset = 0;

  uint32_t nextBreakIndex = 0;
  nsTextFrame* nextBreakBeforeFrame = GetNextBreakBeforeFrame(&nextBreakIndex);
  bool isSVG = nsSVGUtils::IsInSVGTextSubtree(mLineContainer);
  bool enabledJustification =
      (mLineContainer->StyleText()->mTextAlign == NS_STYLE_TEXT_ALIGN_JUSTIFY ||
       mLineContainer->StyleText()->mTextAlignLast ==
           NS_STYLE_TEXT_ALIGN_JUSTIFY);

  const nsStyleText* textStyle = nullptr;
  const nsStyleFont* fontStyle = nullptr;
  ComputedStyle* lastComputedStyle = nullptr;
  for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
    MappedFlow* mappedFlow = &mMappedFlows[i];
    nsTextFrame* f = mappedFlow->mStartFrame;

    lastComputedStyle = f->Style();
    // Detect use of text-transform or font-variant anywhere in the run
    textStyle = f->StyleText();
    if (NS_STYLE_TEXT_TRANSFORM_NONE != textStyle->mTextTransform ||
        // text-combine-upright requires converting from full-width
        // characters to non-full-width correspendent in some cases.
        lastComputedStyle->IsTextCombined()) {
      anyTextTransformStyle = true;
    }
    if (textStyle->HasTextEmphasis()) {
      anyTextEmphasis = true;
    }
    flags |= GetSpacingFlags(f);
    nsTextFrameUtils::CompressionMode compression =
        GetCSSWhitespaceToCompressionMode(f, textStyle);
    if ((enabledJustification || f->ShouldSuppressLineBreak()) &&
        !textStyle->WhiteSpaceIsSignificant() && !isSVG) {
      flags |= gfx::ShapedTextFlags::TEXT_ENABLE_SPACING;
    }
    fontStyle = f->StyleFont();
    nsIFrame* parent = mLineContainer->GetParent();
    if (NS_MATHML_MATHVARIANT_NONE != fontStyle->mMathVariant) {
      if (NS_MATHML_MATHVARIANT_NORMAL != fontStyle->mMathVariant) {
        anyMathMLStyling = true;
      }
    } else if (mLineContainer->GetStateBits() & NS_FRAME_IS_IN_SINGLE_CHAR_MI) {
      flags2 |= nsTextFrameUtils::Flags::TEXT_IS_SINGLE_CHAR_MI;
      anyMathMLStyling = true;
      // Test for fontstyle attribute as StyleFont() may not be accurate
      // To be consistent in terms of ignoring CSS style changes, fontweight
      // gets checked too.
      if (parent) {
        nsIContent* content = parent->GetContent();
        if (content && content->IsElement()) {
          if (content->AsElement()->AttrValueIs(
                  kNameSpaceID_None, nsGkAtoms::fontstyle_,
                  NS_LITERAL_STRING("normal"), eCaseMatters)) {
            mathFlags |= MathMLTextRunFactory::MATH_FONT_STYLING_NORMAL;
          }
          if (content->AsElement()->AttrValueIs(
                  kNameSpaceID_None, nsGkAtoms::fontweight_,
                  NS_LITERAL_STRING("bold"), eCaseMatters)) {
            mathFlags |= MathMLTextRunFactory::MATH_FONT_WEIGHT_BOLD;
          }
        }
      }
    }
    if (mLineContainer->HasAnyStateBits(TEXT_IS_IN_TOKEN_MATHML)) {
      // All MathML tokens except <mtext> use 'math' script.
      if (!(parent && parent->GetContent() &&
            parent->GetContent()->IsMathMLElement(nsGkAtoms::mtext_))) {
        flags |= gfx::ShapedTextFlags::TEXT_USE_MATH_SCRIPT;
      }
      nsIMathMLFrame* mathFrame = do_QueryFrame(parent);
      if (mathFrame) {
        nsPresentationData presData;
        mathFrame->GetPresentationData(presData);
        if (NS_MATHML_IS_DTLS_SET(presData.flags)) {
          mathFlags |= MathMLTextRunFactory::MATH_FONT_FEATURE_DTLS;
          anyMathMLStyling = true;
        }
      }
    }
    nsIFrame* child = mLineContainer;
    uint8_t oldScriptLevel = 0;
    while (parent &&
           child->HasAnyStateBits(NS_FRAME_MATHML_SCRIPT_DESCENDANT)) {
      // Reconstruct the script level ignoring any user overrides. It is
      // calculated this way instead of using scriptlevel to ensure the
      // correct ssty font feature setting is used even if the user sets a
      // different (especially negative) scriptlevel.
      nsIMathMLFrame* mathFrame = do_QueryFrame(parent);
      if (mathFrame) {
        sstyScriptLevel += mathFrame->ScriptIncrement(child);
      }
      if (sstyScriptLevel < oldScriptLevel) {
        // overflow
        sstyScriptLevel = UINT8_MAX;
        break;
      }
      child = parent;
      parent = parent->GetParent();
      oldScriptLevel = sstyScriptLevel;
    }
    if (sstyScriptLevel) {
      anyMathMLStyling = true;
    }

    // Figure out what content is included in this flow.
    nsIContent* content = f->GetContent();
    const nsTextFragment* frag = content->GetText();
    int32_t contentStart = mappedFlow->mStartFrame->GetContentOffset();
    int32_t contentEnd = mappedFlow->GetContentEnd();
    int32_t contentLength = contentEnd - contentStart;

    TextRunMappedFlow* newFlow = &userMappedFlows[i];
    newFlow->mStartFrame = mappedFlow->mStartFrame;
    newFlow->mDOMOffsetToBeforeTransformOffset =
        skipChars.GetOriginalCharCount() -
        mappedFlow->mStartFrame->GetContentOffset();
    newFlow->mContentLength = contentLength;

    while (nextBreakBeforeFrame &&
           nextBreakBeforeFrame->GetContent() == content) {
      textBreakPoints.AppendElement(nextBreakBeforeFrame->GetContentOffset() +
                                    newFlow->mDOMOffsetToBeforeTransformOffset);
      nextBreakBeforeFrame = GetNextBreakBeforeFrame(&nextBreakIndex);
    }

    nsTextFrameUtils::Flags analysisFlags;
    if (frag->Is2b()) {
      NS_ASSERTION(mDoubleByteText, "Wrong buffer char size!");
      char16_t* bufStart = static_cast<char16_t*>(aTextBuffer);
      char16_t* bufEnd = nsTextFrameUtils::TransformText(
          frag->Get2b() + contentStart, contentLength, bufStart, compression,
          &mNextRunContextInfo, &skipChars, &analysisFlags);
      aTextBuffer = bufEnd;
      currentTransformedTextOffset =
          bufEnd - static_cast<const char16_t*>(textPtr);
    } else {
      if (mDoubleByteText) {
        // Need to expand the text. First transform it into a temporary buffer,
        // then expand.
        AutoTArray<uint8_t, BIG_TEXT_NODE_SIZE> tempBuf;
        uint8_t* bufStart = tempBuf.AppendElements(contentLength, fallible);
        if (!bufStart) {
          DestroyUserData(userDataToDestroy);
          return nullptr;
        }
        uint8_t* end = nsTextFrameUtils::TransformText(
            reinterpret_cast<const uint8_t*>(frag->Get1b()) + contentStart,
            contentLength, bufStart, compression, &mNextRunContextInfo,
            &skipChars, &analysisFlags);
        aTextBuffer =
            ExpandBuffer(static_cast<char16_t*>(aTextBuffer),
                         tempBuf.Elements(), end - tempBuf.Elements());
        currentTransformedTextOffset = static_cast<char16_t*>(aTextBuffer) -
                                       static_cast<const char16_t*>(textPtr);
      } else {
        uint8_t* bufStart = static_cast<uint8_t*>(aTextBuffer);
        uint8_t* end = nsTextFrameUtils::TransformText(
            reinterpret_cast<const uint8_t*>(frag->Get1b()) + contentStart,
            contentLength, bufStart, compression, &mNextRunContextInfo,
            &skipChars, &analysisFlags);
        aTextBuffer = end;
        currentTransformedTextOffset =
            end - static_cast<const uint8_t*>(textPtr);
      }
    }
    flags2 |= analysisFlags;
  }

  void* finalUserData;
  if (userData == &dummyData) {
    flags2 |= nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW;
    userData = nullptr;
    finalUserData = mMappedFlows[0].mStartFrame;
  } else {
    finalUserData = userData;
  }

  uint32_t transformedLength = currentTransformedTextOffset;

  // Now build the textrun
  nsTextFrame* firstFrame = mMappedFlows[0].mStartFrame;
  float fontInflation;
  gfxFontGroup* fontGroup;
  if (mWhichTextRun == nsTextFrame::eNotInflated) {
    fontInflation = 1.0f;
    fontGroup = GetFontGroupForFrame(firstFrame, fontInflation);
  } else {
    fontInflation = nsLayoutUtils::FontSizeInflationFor(firstFrame);
    fontGroup = GetInflatedFontGroupForFrame(firstFrame);
  }

  if (!fontGroup) {
    DestroyUserData(userDataToDestroy);
    return nullptr;
  }

  if (flags2 & nsTextFrameUtils::Flags::TEXT_HAS_TAB) {
    flags |= gfx::ShapedTextFlags::TEXT_ENABLE_SPACING;
  }
  if (flags2 & nsTextFrameUtils::Flags::TEXT_HAS_SHY) {
    flags |= gfx::ShapedTextFlags::TEXT_ENABLE_HYPHEN_BREAKS;
  }
  if (mBidiEnabled && (IS_LEVEL_RTL(firstFrame->GetEmbeddingLevel()))) {
    flags |= gfx::ShapedTextFlags::TEXT_IS_RTL;
  }
  if (mNextRunContextInfo & nsTextFrameUtils::INCOMING_WHITESPACE) {
    flags2 |= nsTextFrameUtils::Flags::TEXT_TRAILING_WHITESPACE;
  }
  if (mNextRunContextInfo & nsTextFrameUtils::INCOMING_ARABICCHAR) {
    flags |= gfx::ShapedTextFlags::TEXT_TRAILING_ARABICCHAR;
  }
  // ContinueTextRunAcrossFrames guarantees that it doesn't matter which
  // frame's style is used, so we use a mixture of the first frame and
  // last frame's style
  flags |= nsLayoutUtils::GetTextRunFlagsForStyle(
      lastComputedStyle, firstFrame->PresContext(), fontStyle, textStyle,
      LetterSpacing(firstFrame, textStyle));
  // XXX this is a bit of a hack. For performance reasons, if we're favouring
  // performance over quality, don't try to get accurate glyph extents.
  if (!(flags & gfx::ShapedTextFlags::TEXT_OPTIMIZE_SPEED)) {
    flags |= gfx::ShapedTextFlags::TEXT_NEED_BOUNDING_BOX;
  }

  // Convert linebreak coordinates to transformed string offsets
  NS_ASSERTION(nextBreakIndex == mLineBreakBeforeFrames.Length(),
               "Didn't find all the frames to break-before...");
  gfxSkipCharsIterator iter(skipChars);
  AutoTArray<uint32_t, 50> textBreakPointsAfterTransform;
  for (uint32_t i = 0; i < textBreakPoints.Length(); ++i) {
    nsTextFrameUtils::AppendLineBreakOffset(
        &textBreakPointsAfterTransform,
        iter.ConvertOriginalToSkipped(textBreakPoints[i]));
  }
  if (mStartOfLine) {
    nsTextFrameUtils::AppendLineBreakOffset(&textBreakPointsAfterTransform,
                                            transformedLength);
  }

  // Setup factory chain
  UniquePtr<nsTransformingTextRunFactory> transformingFactory;
  if (anyTextTransformStyle) {
    transformingFactory = MakeUnique<nsCaseTransformTextRunFactory>(
        std::move(transformingFactory));
  }
  if (anyMathMLStyling) {
    transformingFactory = MakeUnique<MathMLTextRunFactory>(
        std::move(transformingFactory), mathFlags, sstyScriptLevel,
        fontInflation);
  }
  nsTArray<RefPtr<nsTransformedCharStyle>> styles;
  if (transformingFactory) {
    iter.SetOriginalOffset(0);
    for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
      MappedFlow* mappedFlow = &mMappedFlows[i];
      nsTextFrame* f;
      ComputedStyle* sc = nullptr;
      RefPtr<nsTransformedCharStyle> charStyle;
      for (f = mappedFlow->mStartFrame; f != mappedFlow->mEndFrame;
           f = f->GetNextContinuation()) {
        uint32_t offset = iter.GetSkippedOffset();
        iter.AdvanceOriginal(f->GetContentLength());
        uint32_t end = iter.GetSkippedOffset();
        // Text-combined frames have content-dependent transform, so we
        // want to create new nsTransformedCharStyle for them anyway.
        if (sc != f->Style() || sc->IsTextCombined()) {
          sc = f->Style();
          charStyle = new nsTransformedCharStyle(sc, f->PresContext());
          if (sc->IsTextCombined() && f->CountGraphemeClusters() > 1) {
            charStyle->mForceNonFullWidth = true;
          }
        }
        uint32_t j;
        for (j = offset; j < end; ++j) {
          styles.AppendElement(charStyle);
        }
      }
    }
    flags2 |= nsTextFrameUtils::Flags::TEXT_IS_TRANSFORMED;
    NS_ASSERTION(iter.GetSkippedOffset() == transformedLength,
                 "We didn't cover all the characters in the text run!");
  }

  RefPtr<gfxTextRun> textRun;
  gfxTextRunFactory::Parameters params = {
      mDrawTarget,
      finalUserData,
      &skipChars,
      textBreakPointsAfterTransform.Elements(),
      uint32_t(textBreakPointsAfterTransform.Length()),
      int32_t(firstFrame->PresContext()->AppUnitsPerDevPixel())};

  if (mDoubleByteText) {
    const char16_t* text = static_cast<const char16_t*>(textPtr);
    if (transformingFactory) {
      textRun = transformingFactory->MakeTextRun(
          text, transformedLength, &params, fontGroup, flags, flags2,
          std::move(styles), true);
      if (textRun) {
        // ownership of the factory has passed to the textrun
        // TODO: bug 1285316: clean up ownership transfer from the factory to
        // the textrun
        Unused << transformingFactory.release();
      }
    } else {
      textRun = fontGroup->MakeTextRun(text, transformedLength, &params, flags,
                                       flags2, mMissingFonts);
    }
  } else {
    const uint8_t* text = static_cast<const uint8_t*>(textPtr);
    flags |= gfx::ShapedTextFlags::TEXT_IS_8BIT;
    if (transformingFactory) {
      textRun = transformingFactory->MakeTextRun(
          text, transformedLength, &params, fontGroup, flags, flags2,
          std::move(styles), true);
      if (textRun) {
        // ownership of the factory has passed to the textrun
        // TODO: bug 1285316: clean up ownership transfer from the factory to
        // the textrun
        Unused << transformingFactory.release();
      }
    } else {
      textRun = fontGroup->MakeTextRun(text, transformedLength, &params, flags,
                                       flags2, mMissingFonts);
    }
  }
  if (!textRun) {
    DestroyUserData(userDataToDestroy);
    return nullptr;
  }

  // We have to set these up after we've created the textrun, because
  // the breaks may be stored in the textrun during this very call.
  // This is a bit annoying because it requires another loop over the frames
  // making up the textrun, but I don't see a way to avoid this.
  SetupBreakSinksForTextRun(textRun.get(), textPtr);

  if (anyTextEmphasis) {
    SetupTextEmphasisForTextRun(textRun.get(), textPtr);
  }

  if (mSkipIncompleteTextRuns) {
    mSkipIncompleteTextRuns = !TextContainsLineBreakerWhiteSpace(
        textPtr, transformedLength, mDoubleByteText);
    // Since we're doing to destroy the user data now, avoid a dangling
    // pointer. Strictly speaking we don't need to do this since it should
    // not be used (since this textrun will not be used and will be
    // itself deleted soon), but it's always better to not have dangling
    // pointers around.
    textRun->SetUserData(nullptr);
    DestroyUserData(userDataToDestroy);
    return nullptr;
  }

  // Actually wipe out the textruns associated with the mapped frames and
  // associate those frames with this text run.
  AssignTextRun(textRun.get(), fontInflation);
  return textRun.forget();
}

// This is a cut-down version of BuildTextRunForFrames used to set up
// context for the line-breaker, when the textrun has already been created.
// So it does the same walk over the mMappedFlows, but doesn't actually
// build a new textrun.
bool BuildTextRunsScanner::SetupLineBreakerContext(gfxTextRun* aTextRun) {
  AutoTArray<uint8_t, BIG_TEXT_NODE_SIZE> buffer;
  uint32_t bufferSize = mMaxTextLength * (mDoubleByteText ? 2 : 1);
  if (bufferSize < mMaxTextLength || bufferSize == UINT32_MAX) {
    return false;
  }
  void* textPtr = buffer.AppendElements(bufferSize, fallible);
  if (!textPtr) {
    return false;
  }

  gfxSkipChars skipChars;

  for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
    MappedFlow* mappedFlow = &mMappedFlows[i];
    nsTextFrame* f = mappedFlow->mStartFrame;

    const nsStyleText* textStyle = f->StyleText();
    nsTextFrameUtils::CompressionMode compression =
        GetCSSWhitespaceToCompressionMode(f, textStyle);

    // Figure out what content is included in this flow.
    nsIContent* content = f->GetContent();
    const nsTextFragment* frag = content->GetText();
    int32_t contentStart = mappedFlow->mStartFrame->GetContentOffset();
    int32_t contentEnd = mappedFlow->GetContentEnd();
    int32_t contentLength = contentEnd - contentStart;

    nsTextFrameUtils::Flags analysisFlags;
    if (frag->Is2b()) {
      NS_ASSERTION(mDoubleByteText, "Wrong buffer char size!");
      char16_t* bufStart = static_cast<char16_t*>(textPtr);
      char16_t* bufEnd = nsTextFrameUtils::TransformText(
          frag->Get2b() + contentStart, contentLength, bufStart, compression,
          &mNextRunContextInfo, &skipChars, &analysisFlags);
      textPtr = bufEnd;
    } else {
      if (mDoubleByteText) {
        // Need to expand the text. First transform it into a temporary buffer,
        // then expand.
        AutoTArray<uint8_t, BIG_TEXT_NODE_SIZE> tempBuf;
        uint8_t* bufStart = tempBuf.AppendElements(contentLength, fallible);
        if (!bufStart) {
          return false;
        }
        uint8_t* end = nsTextFrameUtils::TransformText(
            reinterpret_cast<const uint8_t*>(frag->Get1b()) + contentStart,
            contentLength, bufStart, compression, &mNextRunContextInfo,
            &skipChars, &analysisFlags);
        textPtr = ExpandBuffer(static_cast<char16_t*>(textPtr),
                               tempBuf.Elements(), end - tempBuf.Elements());
      } else {
        uint8_t* bufStart = static_cast<uint8_t*>(textPtr);
        uint8_t* end = nsTextFrameUtils::TransformText(
            reinterpret_cast<const uint8_t*>(frag->Get1b()) + contentStart,
            contentLength, bufStart, compression, &mNextRunContextInfo,
            &skipChars, &analysisFlags);
        textPtr = end;
      }
    }
  }

  // We have to set these up after we've created the textrun, because
  // the breaks may be stored in the textrun during this very call.
  // This is a bit annoying because it requires another loop over the frames
  // making up the textrun, but I don't see a way to avoid this.
  SetupBreakSinksForTextRun(aTextRun, buffer.Elements());

  return true;
}

static bool HasCompressedLeadingWhitespace(
    nsTextFrame* aFrame, const nsStyleText* aStyleText,
    int32_t aContentEndOffset, const gfxSkipCharsIterator& aIterator) {
  if (!aIterator.IsOriginalCharSkipped()) return false;

  gfxSkipCharsIterator iter = aIterator;
  int32_t frameContentOffset = aFrame->GetContentOffset();
  const nsTextFragment* frag = aFrame->GetContent()->GetText();
  while (frameContentOffset < aContentEndOffset &&
         iter.IsOriginalCharSkipped()) {
    if (IsTrimmableSpace(frag, frameContentOffset, aStyleText)) return true;
    ++frameContentOffset;
    iter.AdvanceOriginal(1);
  }
  return false;
}

void BuildTextRunsScanner::SetupBreakSinksForTextRun(gfxTextRun* aTextRun,
                                                     const void* aTextPtr) {
  using mozilla::intl::LineBreaker;

  // for word-break style
  switch (mLineContainer->StyleText()->mWordBreak) {
    case NS_STYLE_WORDBREAK_BREAK_ALL:
      mLineBreaker.SetWordBreak(LineBreaker::kWordBreak_BreakAll);
      break;
    case NS_STYLE_WORDBREAK_KEEP_ALL:
      mLineBreaker.SetWordBreak(LineBreaker::kWordBreak_KeepAll);
      break;
    default:
      mLineBreaker.SetWordBreak(LineBreaker::kWordBreak_Normal);
      break;
  }

  // textruns have uniform language
  const nsStyleFont* styleFont = mMappedFlows[0].mStartFrame->StyleFont();
  // We should only use a language for hyphenation if it was specified
  // explicitly.
  nsAtom* hyphenationLanguage =
      styleFont->mExplicitLanguage ? styleFont->mLanguage.get() : nullptr;
  // We keep this pointed at the skip-chars data for the current mappedFlow.
  // This lets us cheaply check whether the flow has compressed initial
  // whitespace...
  gfxSkipCharsIterator iter(aTextRun->GetSkipChars());

  for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
    MappedFlow* mappedFlow = &mMappedFlows[i];
    uint32_t offset = iter.GetSkippedOffset();
    gfxSkipCharsIterator iterNext = iter;
    iterNext.AdvanceOriginal(mappedFlow->GetContentEnd() -
                             mappedFlow->mStartFrame->GetContentOffset());

    UniquePtr<BreakSink>* breakSink = mBreakSinks.AppendElement(
        MakeUnique<BreakSink>(aTextRun, mDrawTarget, offset));
    if (!breakSink || !*breakSink) return;

    uint32_t length = iterNext.GetSkippedOffset() - offset;
    uint32_t flags = 0;
    nsIFrame* initialBreakController =
        mappedFlow->mAncestorControllingInitialBreak;
    if (!initialBreakController) {
      initialBreakController = mLineContainer;
    }
    if (!initialBreakController->StyleText()->WhiteSpaceCanWrap(
            initialBreakController)) {
      flags |= nsLineBreaker::BREAK_SUPPRESS_INITIAL;
    }
    nsTextFrame* startFrame = mappedFlow->mStartFrame;
    const nsStyleText* textStyle = startFrame->StyleText();
    if (!textStyle->WhiteSpaceCanWrap(startFrame)) {
      flags |= nsLineBreaker::BREAK_SUPPRESS_INSIDE;
    }
    if (aTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_NO_BREAKS) {
      flags |= nsLineBreaker::BREAK_SKIP_SETTING_NO_BREAKS;
    }
    if (textStyle->mTextTransform == NS_STYLE_TEXT_TRANSFORM_CAPITALIZE) {
      flags |= nsLineBreaker::BREAK_NEED_CAPITALIZATION;
    }
    if (textStyle->mHyphens == StyleHyphens::Auto) {
      flags |= nsLineBreaker::BREAK_USE_AUTO_HYPHENATION;
    }

    if (HasCompressedLeadingWhitespace(startFrame, textStyle,
                                       mappedFlow->GetContentEnd(), iter)) {
      mLineBreaker.AppendInvisibleWhitespace(flags);
    }

    if (length > 0) {
      BreakSink* sink = mSkipIncompleteTextRuns ? nullptr : (*breakSink).get();
      if (mDoubleByteText) {
        const char16_t* text = reinterpret_cast<const char16_t*>(aTextPtr);
        mLineBreaker.AppendText(hyphenationLanguage, text + offset, length,
                                flags, sink);
      } else {
        const uint8_t* text = reinterpret_cast<const uint8_t*>(aTextPtr);
        mLineBreaker.AppendText(hyphenationLanguage, text + offset, length,
                                flags, sink);
      }
    }

    iter = iterNext;
  }
}

static bool MayCharacterHaveEmphasisMark(uint32_t aCh) {
  auto category = unicode::GetGeneralCategory(aCh);
  // Comparing an unsigned variable against zero is a compile error,
  // so we use static assert here to ensure we really don't need to
  // compare it with the given constant.
  static_assert(IsUnsigned<decltype(category)>::value &&
                    HB_UNICODE_GENERAL_CATEGORY_CONTROL == 0,
                "if this constant is not zero, or category is signed, "
                "we need to explicitly do the comparison below");
  return !(category <= HB_UNICODE_GENERAL_CATEGORY_UNASSIGNED ||
           (category >= HB_UNICODE_GENERAL_CATEGORY_LINE_SEPARATOR &&
            category <= HB_UNICODE_GENERAL_CATEGORY_SPACE_SEPARATOR));
}

static bool MayCharacterHaveEmphasisMark(uint8_t aCh) {
  // 0x00~0x1f and 0x7f~0x9f are in category Cc
  // 0x20 and 0xa0 are in category Zs
  bool result = !(aCh <= 0x20 || (aCh >= 0x7f && aCh <= 0xa0));
  MOZ_ASSERT(result == MayCharacterHaveEmphasisMark(uint32_t(aCh)),
             "result for uint8_t should match result for uint32_t");
  return result;
}

void BuildTextRunsScanner::SetupTextEmphasisForTextRun(gfxTextRun* aTextRun,
                                                       const void* aTextPtr) {
  if (!mDoubleByteText) {
    auto text = reinterpret_cast<const uint8_t*>(aTextPtr);
    for (auto i : IntegerRange(aTextRun->GetLength())) {
      if (!MayCharacterHaveEmphasisMark(text[i])) {
        aTextRun->SetNoEmphasisMark(i);
      }
    }
  } else {
    auto text = reinterpret_cast<const char16_t*>(aTextPtr);
    auto length = aTextRun->GetLength();
    for (size_t i = 0; i < length; ++i) {
      if (NS_IS_HIGH_SURROGATE(text[i]) && i + 1 < length &&
          NS_IS_LOW_SURROGATE(text[i + 1])) {
        uint32_t ch = SURROGATE_TO_UCS4(text[i], text[i + 1]);
        if (!MayCharacterHaveEmphasisMark(ch)) {
          aTextRun->SetNoEmphasisMark(i);
          aTextRun->SetNoEmphasisMark(i + 1);
        }
        ++i;
      } else {
        if (!MayCharacterHaveEmphasisMark(uint32_t(text[i]))) {
          aTextRun->SetNoEmphasisMark(i);
        }
      }
    }
  }
}

// Find the flow corresponding to aContent in aUserData
static inline TextRunMappedFlow* FindFlowForContent(
    TextRunUserData* aUserData, nsIContent* aContent,
    TextRunMappedFlow* userMappedFlows) {
  // Find the flow that contains us
  int32_t i = aUserData->mLastFlowIndex;
  int32_t delta = 1;
  int32_t sign = 1;
  // Search starting at the current position and examine close-by
  // positions first, moving further and further away as we go.
  while (i >= 0 && uint32_t(i) < aUserData->mMappedFlowCount) {
    TextRunMappedFlow* flow = &userMappedFlows[i];
    if (flow->mStartFrame->GetContent() == aContent) {
      return flow;
    }

    i += delta;
    sign = -sign;
    delta = -delta + sign;
  }

  // We ran into an array edge.  Add |delta| to |i| once more to get
  // back to the side where we still need to search, then step in
  // the |sign| direction.
  i += delta;
  if (sign > 0) {
    for (; i < int32_t(aUserData->mMappedFlowCount); ++i) {
      TextRunMappedFlow* flow = &userMappedFlows[i];
      if (flow->mStartFrame->GetContent() == aContent) {
        return flow;
      }
    }
  } else {
    for (; i >= 0; --i) {
      TextRunMappedFlow* flow = &userMappedFlows[i];
      if (flow->mStartFrame->GetContent() == aContent) {
        return flow;
      }
    }
  }

  return nullptr;
}

void BuildTextRunsScanner::AssignTextRun(gfxTextRun* aTextRun,
                                         float aInflation) {
  for (uint32_t i = 0; i < mMappedFlows.Length(); ++i) {
    MappedFlow* mappedFlow = &mMappedFlows[i];
    nsTextFrame* startFrame = mappedFlow->mStartFrame;
    nsTextFrame* endFrame = mappedFlow->mEndFrame;
    nsTextFrame* f;
    for (f = startFrame; f != endFrame; f = f->GetNextContinuation()) {
#ifdef DEBUG_roc
      if (f->GetTextRun(mWhichTextRun)) {
        gfxTextRun* textRun = f->GetTextRun(mWhichTextRun);
        if (textRun->GetFlags2() &
            nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
          if (mMappedFlows[0].mStartFrame != GetFrameForSimpleFlow(textRun)) {
            NS_WARNING("REASSIGNING SIMPLE FLOW TEXT RUN!");
          }
        } else {
          auto userData =
              static_cast<TextRunUserData*>(aTextRun->GetUserData());
          TextRunMappedFlow* userMappedFlows = GetMappedFlows(aTextRun);
          if (userData->mMappedFlowCount >= mMappedFlows.Length() ||
              userMappedFlows[userData->mMappedFlowCount - 1].mStartFrame !=
                  mMappedFlows[userdata->mMappedFlowCount - 1].mStartFrame) {
            NS_WARNING("REASSIGNING MULTIFLOW TEXT RUN (not append)!");
          }
        }
      }
#endif

      gfxTextRun* oldTextRun = f->GetTextRun(mWhichTextRun);
      if (oldTextRun) {
        nsTextFrame* firstFrame = nullptr;
        uint32_t startOffset = 0;
        if (oldTextRun->GetFlags2() &
            nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
          firstFrame = GetFrameForSimpleFlow(oldTextRun);
        } else {
          auto userData =
              static_cast<TextRunUserData*>(oldTextRun->GetUserData());
          TextRunMappedFlow* userMappedFlows = GetMappedFlows(oldTextRun);
          firstFrame = userMappedFlows[0].mStartFrame;
          if (MOZ_UNLIKELY(f != firstFrame)) {
            TextRunMappedFlow* flow =
                FindFlowForContent(userData, f->GetContent(), userMappedFlows);
            if (flow) {
              startOffset = flow->mDOMOffsetToBeforeTransformOffset;
            } else {
              NS_ERROR("Can't find flow containing frame 'f'");
            }
          }
        }

        // Optimization: if |f| is the first frame in the flow then there are no
        // prev-continuations that use |oldTextRun|.
        nsTextFrame* clearFrom = nullptr;
        if (MOZ_UNLIKELY(f != firstFrame)) {
          // If all the frames in the mapped flow starting at |f| (inclusive)
          // are empty then we let the prev-continuations keep the old text run.
          gfxSkipCharsIterator iter(oldTextRun->GetSkipChars(), startOffset,
                                    f->GetContentOffset());
          uint32_t textRunOffset =
              iter.ConvertOriginalToSkipped(f->GetContentOffset());
          clearFrom = textRunOffset == oldTextRun->GetLength() ? f : nullptr;
        }
        f->ClearTextRun(clearFrom, mWhichTextRun);

#ifdef DEBUG
        if (firstFrame && !firstFrame->GetTextRun(mWhichTextRun)) {
          // oldTextRun was destroyed - assert that we don't reference it.
          for (uint32_t j = 0; j < mBreakSinks.Length(); ++j) {
            NS_ASSERTION(oldTextRun != mBreakSinks[j]->mTextRun,
                         "destroyed text run is still in use");
          }
        }
#endif
      }
      f->SetTextRun(aTextRun, mWhichTextRun, aInflation);
    }
    // Set this bit now; we can't set it any earlier because
    // f->ClearTextRun() might clear it out.
    nsFrameState whichTextRunState =
        startFrame->GetTextRun(nsTextFrame::eInflated) == aTextRun
            ? TEXT_IN_TEXTRUN_USER_DATA
            : TEXT_IN_UNINFLATED_TEXTRUN_USER_DATA;
    startFrame->AddStateBits(whichTextRunState);
  }
}

NS_QUERYFRAME_HEAD(nsTextFrame)
  NS_QUERYFRAME_ENTRY(nsTextFrame)
NS_QUERYFRAME_TAIL_INHERITING(nsFrame)

gfxSkipCharsIterator nsTextFrame::EnsureTextRun(
    TextRunType aWhichTextRun, DrawTarget* aRefDrawTarget,
    nsIFrame* aLineContainer, const nsLineList::iterator* aLine,
    uint32_t* aFlowEndInTextRun) {
  gfxTextRun* textRun = GetTextRun(aWhichTextRun);
  if (!textRun || (aLine && (*aLine)->GetInvalidateTextRuns())) {
    RefPtr<DrawTarget> refDT = aRefDrawTarget;
    if (!refDT) {
      refDT = CreateReferenceDrawTarget(this);
    }
    if (refDT) {
      BuildTextRuns(refDT, this, aLineContainer, aLine, aWhichTextRun);
    }
    textRun = GetTextRun(aWhichTextRun);
    if (!textRun) {
      // A text run was not constructed for this frame. This is bad. The caller
      // will check mTextRun.
      return gfxSkipCharsIterator(gfxPlatform::GetPlatform()->EmptySkipChars(),
                                  0);
    }
    TabWidthStore* tabWidths = GetProperty(TabWidthProperty());
    if (tabWidths && tabWidths->mValidForContentOffset != GetContentOffset()) {
      DeleteProperty(TabWidthProperty());
    }
  }

  if (textRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_IS_SIMPLE_FLOW) {
    if (aFlowEndInTextRun) {
      *aFlowEndInTextRun = textRun->GetLength();
    }
    return gfxSkipCharsIterator(textRun->GetSkipChars(), 0, mContentOffset);
  }

  auto userData = static_cast<TextRunUserData*>(textRun->GetUserData());
  TextRunMappedFlow* userMappedFlows = GetMappedFlows(textRun);
  TextRunMappedFlow* flow =
      FindFlowForContent(userData, mContent, userMappedFlows);
  if (flow) {
    // Since textruns can only contain one flow for a given content element,
    // this must be our flow.
    uint32_t flowIndex = flow - userMappedFlows;
    userData->mLastFlowIndex = flowIndex;
    gfxSkipCharsIterator iter(textRun->GetSkipChars(),
                              flow->mDOMOffsetToBeforeTransformOffset,
                              mContentOffset);
    if (aFlowEndInTextRun) {
      if (flowIndex + 1 < userData->mMappedFlowCount) {
        gfxSkipCharsIterator end(textRun->GetSkipChars());
        *aFlowEndInTextRun = end.ConvertOriginalToSkipped(
            flow[1].mStartFrame->GetContentOffset() +
            flow[1].mDOMOffsetToBeforeTransformOffset);
      } else {
        *aFlowEndInTextRun = textRun->GetLength();
      }
    }
    return iter;
  }

  NS_ERROR("Can't find flow containing this frame???");
  return gfxSkipCharsIterator(gfxPlatform::GetPlatform()->EmptySkipChars(), 0);
}

static uint32_t GetEndOfTrimmedText(const nsTextFragment* aFrag,
                                    const nsStyleText* aStyleText,
                                    uint32_t aStart, uint32_t aEnd,
                                    gfxSkipCharsIterator* aIterator) {
  aIterator->SetSkippedOffset(aEnd);
  while (aIterator->GetSkippedOffset() > aStart) {
    aIterator->AdvanceSkipped(-1);
    if (!IsTrimmableSpace(aFrag, aIterator->GetOriginalOffset(), aStyleText))
      return aIterator->GetSkippedOffset() + 1;
  }
  return aStart;
}

nsTextFrame::TrimmedOffsets nsTextFrame::GetTrimmedOffsets(
    const nsTextFragment* aFrag, bool aTrimAfter, bool aPostReflow) const {
  NS_ASSERTION(mTextRun, "Need textrun here");
  if (aPostReflow) {
    // This should not be used during reflow. We need our TEXT_REFLOW_FLAGS
    // to be set correctly.  If our parent wasn't reflowed due to the frame
    // tree being too deep then the return value doesn't matter.
    NS_ASSERTION(
        !(GetStateBits() & NS_FRAME_FIRST_REFLOW) ||
            (GetParent()->GetStateBits() & NS_FRAME_TOO_DEEP_IN_FRAME_TREE),
        "Can only call this on frames that have been reflowed");
    NS_ASSERTION(!(GetStateBits() & NS_FRAME_IN_REFLOW),
                 "Can only call this on frames that are not being reflowed");
  }

  TrimmedOffsets offsets = {GetContentOffset(), GetContentLength()};
  const nsStyleText* textStyle = StyleText();
  // Note that pre-line newlines should still allow us to trim spaces
  // for display
  if (textStyle->WhiteSpaceIsSignificant()) return offsets;

  if (!aPostReflow || (GetStateBits() & TEXT_START_OF_LINE)) {
    int32_t whitespaceCount =
        GetTrimmableWhitespaceCount(aFrag, offsets.mStart, offsets.mLength, 1);
    offsets.mStart += whitespaceCount;
    offsets.mLength -= whitespaceCount;
  }

  if (aTrimAfter && (!aPostReflow || (GetStateBits() & TEXT_END_OF_LINE))) {
    // This treats a trailing 'pre-line' newline as trimmable. That's fine,
    // it's actually what we want since we want whitespace before it to
    // be trimmed.
    int32_t whitespaceCount = GetTrimmableWhitespaceCount(
        aFrag, offsets.GetEnd() - 1, offsets.mLength, -1);
    offsets.mLength -= whitespaceCount;
  }
  return offsets;
}

static bool IsJustifiableCharacter(const nsStyleText* aTextStyle,
                                   const nsTextFragment* aFrag, int32_t aPos,
                                   bool aLangIsCJ) {
  NS_ASSERTION(aPos >= 0, "negative position?!");

  StyleTextJustify justifyStyle = aTextStyle->mTextJustify;
  if (justifyStyle == StyleTextJustify::None) {
    return false;
  }

  char16_t ch = aFrag->CharAt(aPos);
  if (ch == '\n' || ch == '\t' || ch == '\r') {
    return true;
  }
  if (ch == ' ' || ch == CH_NBSP) {
    // Don't justify spaces that are combined with diacriticals
    if (!aFrag->Is2b()) {
      return true;
    }
    return !nsTextFrameUtils::IsSpaceCombiningSequenceTail(
        aFrag->Get2b() + aPos + 1, aFrag->GetLength() - (aPos + 1));
  }

  if (justifyStyle == StyleTextJustify::InterCharacter) {
    return true;
  } else if (justifyStyle == StyleTextJustify::InterWord) {
    return false;
  }

  // text-justify: auto
  if (ch < 0x2150u) {
    return false;
  }
  if (aLangIsCJ) {
    if (  // Number Forms, Arrows, Mathematical Operators
        (0x2150u <= ch && ch <= 0x22ffu) ||
        // Enclosed Alphanumerics
        (0x2460u <= ch && ch <= 0x24ffu) ||
        // Block Elements, Geometric Shapes, Miscellaneous Symbols, Dingbats
        (0x2580u <= ch && ch <= 0x27bfu) ||
        // Supplemental Arrows-A, Braille Patterns, Supplemental Arrows-B,
        // Miscellaneous Mathematical Symbols-B,
        // Supplemental Mathematical Operators, Miscellaneous Symbols and Arrows
        (0x27f0u <= ch && ch <= 0x2bffu) ||
        // CJK Radicals Supplement, CJK Radicals Supplement, Ideographic
        // Description Characters, CJK Symbols and Punctuation, Hiragana,
        // Katakana, Bopomofo
        (0x2e80u <= ch && ch <= 0x312fu) ||
        // Kanbun, Bopomofo Extended, Katakana Phonetic Extensions,
        // Enclosed CJK Letters and Months, CJK Compatibility,
        // CJK Unified Ideographs Extension A, Yijing Hexagram Symbols,
        // CJK Unified Ideographs, Yi Syllables, Yi Radicals
        (0x3190u <= ch && ch <= 0xabffu) ||
        // CJK Compatibility Ideographs
        (0xf900u <= ch && ch <= 0xfaffu) ||
        // Halfwidth and Fullwidth Forms (a part)
        (0xff5eu <= ch && ch <= 0xff9fu)) {
      return true;
    }
    char16_t ch2;
    if (NS_IS_HIGH_SURROGATE(ch) && aFrag->GetLength() > uint32_t(aPos) + 1 &&
        NS_IS_LOW_SURROGATE(ch2 = aFrag->CharAt(aPos + 1))) {
      uint32_t u = SURROGATE_TO_UCS4(ch, ch2);
      // CJK Unified Ideographs Extension B,
      // CJK Unified Ideographs Extension C,
      // CJK Unified Ideographs Extension D,
      // CJK Compatibility Ideographs Supplement
      if (0x20000u <= u && u <= 0x2ffffu) {
        return true;
      }
    }
  }
  return false;
}

void nsTextFrame::ClearMetrics(ReflowOutput& aMetrics) {
  aMetrics.ClearSize();
  aMetrics.SetBlockStartAscent(0);
  mAscent = 0;

  AddStateBits(TEXT_NO_RENDERED_GLYPHS);
}

static int32_t FindChar(const nsTextFragment* frag, int32_t aOffset,
                        int32_t aLength, char16_t ch) {
  int32_t i = 0;
  if (frag->Is2b()) {
    const char16_t* str = frag->Get2b() + aOffset;
    for (; i < aLength; ++i) {
      if (*str == ch) return i + aOffset;
      ++str;
    }
  } else {
    if (uint16_t(ch) <= 0xFF) {
      const char* str = frag->Get1b() + aOffset;
      const void* p = memchr(str, ch, aLength);
      if (p) return (static_cast<const char*>(p) - str) + aOffset;
    }
  }
  return -1;
}

static bool IsChineseOrJapanese(const nsTextFrame* aFrame) {
  if (aFrame->ShouldSuppressLineBreak()) {
    // Always treat ruby as CJ language so that those characters can
    // be expanded properly even when surrounded by other language.
    return true;
  }

  nsAtom* language = aFrame->StyleFont()->mLanguage;
  if (!language) {
    return false;
  }
  return nsStyleUtil::MatchesLanguagePrefix(language, u"ja") ||
         nsStyleUtil::MatchesLanguagePrefix(language, u"zh");
}

#ifdef DEBUG
static bool IsInBounds(const gfxSkipCharsIterator& aStart,
                       int32_t aContentLength, gfxTextRun::Range aRange) {
  if (aStart.GetSkippedOffset() > aRange.start) return false;
  if (aContentLength == INT32_MAX) return true;
  gfxSkipCharsIterator iter(aStart);
  iter.AdvanceOriginal(aContentLength);
  return iter.GetSkippedOffset() >= aRange.end;
}
#endif

class MOZ_STACK_CLASS PropertyProvider final
    : public gfxTextRun::PropertyProvider {
  typedef gfxTextRun::Range Range;
  typedef gfxTextRun::HyphenType HyphenType;

 public:
  /**
   * Use this constructor for reflow, when we don't know what text is
   * really mapped by the frame and we have a lot of other data around.
   *
   * @param aLength can be INT32_MAX to indicate we cover all the text
   * associated with aFrame up to where its flow chain ends in the given
   * textrun. If INT32_MAX is passed, justification and hyphen-related methods
   * cannot be called, nor can GetOriginalLength().
   */
  PropertyProvider(gfxTextRun* aTextRun, const nsStyleText* aTextStyle,
                   const nsTextFragment* aFrag, nsTextFrame* aFrame,
                   const gfxSkipCharsIterator& aStart, int32_t aLength,
                   nsIFrame* aLineContainer,
                   nscoord aOffsetFromBlockOriginForTabs,
                   nsTextFrame::TextRunType aWhichTextRun)
      : mTextRun(aTextRun),
        mFontGroup(nullptr),
        mTextStyle(aTextStyle),
        mFrag(aFrag),
        mLineContainer(aLineContainer),
        mFrame(aFrame),
        mStart(aStart),
        mTempIterator(aStart),
        mTabWidths(nullptr),
        mTabWidthsAnalyzedLimit(0),
        mLength(aLength),
        mWordSpacing(WordSpacing(aFrame, mTextRun, aTextStyle)),
        mLetterSpacing(LetterSpacing(aFrame, aTextStyle)),
        mMinTabAdvance(-1.0),
        mHyphenWidth(-1),
        mOffsetFromBlockOriginForTabs(aOffsetFromBlockOriginForTabs),
        mJustificationArrayStart(0),
        mReflowing(true),
        mWhichTextRun(aWhichTextRun) {
    NS_ASSERTION(mStart.IsInitialized(), "Start not initialized?");
  }

  /**
   * Use this constructor after the frame has been reflowed and we don't
   * have other data around. Gets everything from the frame. EnsureTextRun
   * *must* be called before this!!!
   */
  PropertyProvider(nsTextFrame* aFrame, const gfxSkipCharsIterator& aStart,
                   nsTextFrame::TextRunType aWhichTextRun,
                   nsFontMetrics* aFontMetrics)
      : mTextRun(aFrame->GetTextRun(aWhichTextRun)),
        mFontGroup(nullptr),
        mFontMetrics(aFontMetrics),
        mTextStyle(aFrame->StyleText()),
        mFrag(aFrame->GetContent()->GetText()),
        mLineContainer(nullptr),
        mFrame(aFrame),
        mStart(aStart),
        mTempIterator(aStart),
        mTabWidths(nullptr),
        mTabWidthsAnalyzedLimit(0),
        mLength(aFrame->GetContentLength()),
        mWordSpacing(WordSpacing(aFrame, mTextRun)),
        mLetterSpacing(LetterSpacing(aFrame)),
        mMinTabAdvance(-1.0),
        mHyphenWidth(-1),
        mOffsetFromBlockOriginForTabs(0),
        mJustificationArrayStart(0),
        mReflowing(false),
        mWhichTextRun(aWhichTextRun) {
    NS_ASSERTION(mTextRun, "Textrun not initialized!");
  }

  // Call this after construction if you're not going to reflow the text
  void InitializeForDisplay(bool aTrimAfter);

  void InitializeForMeasure();

  void GetSpacing(Range aRange, Spacing* aSpacing) const final;
  gfxFloat GetHyphenWidth() const final;
  void GetHyphenationBreaks(Range aRange, HyphenType* aBreakBefore) const final;
  StyleHyphens GetHyphensOption() const final { return mTextStyle->mHyphens; }

  already_AddRefed<DrawTarget> GetDrawTarget() const final {
    return CreateReferenceDrawTarget(GetFrame());
  }

  uint32_t GetAppUnitsPerDevUnit() const final {
    return mTextRun->GetAppUnitsPerDevUnit();
  }

  void GetSpacingInternal(Range aRange, Spacing* aSpacing,
                          bool aIgnoreTabs) const;

  /**
   * Compute the justification information in given DOM range, return
   * justification info and assignments if requested.
   */
  JustificationInfo ComputeJustification(
      Range aRange, nsTArray<JustificationAssignment>* aAssignments = nullptr);

  const nsTextFrame* GetFrame() const { return mFrame; }
  // This may not be equal to the frame offset/length in because we may have
  // adjusted for whitespace trimming according to the state bits set in the
  // frame (for the static provider)
  const gfxSkipCharsIterator& GetStart() const { return mStart; }
  // May return INT32_MAX if that was given to the constructor
  uint32_t GetOriginalLength() const {
    NS_ASSERTION(mLength != INT32_MAX, "Length not known");
    return mLength;
  }
  const nsTextFragment* GetFragment() const { return mFrag; }

  gfxFontGroup* GetFontGroup() const {
    if (!mFontGroup) {
      mFontGroup = GetFontMetrics()->GetThebesFontGroup();
    }
    return mFontGroup;
  }

  nsFontMetrics* GetFontMetrics() const {
    if (!mFontMetrics) {
      InitFontGroupAndFontMetrics();
    }
    return mFontMetrics;
  }

  void CalcTabWidths(Range aTransformedRange, gfxFloat aTabWidth) const;

  gfxFloat MinTabAdvance() const {
    if (mMinTabAdvance < 0.0) {
      mMinTabAdvance = GetMinTabAdvanceAppUnits(mTextRun);
    }
    return mMinTabAdvance;
  }

  const gfxSkipCharsIterator& GetEndHint() const { return mTempIterator; }

 protected:
  void SetupJustificationSpacing(bool aPostReflow);

  void InitFontGroupAndFontMetrics() const {
    if (!mFontMetrics) {
      if (mWhichTextRun == nsTextFrame::eInflated) {
        if (!mFrame->InflatedFontMetrics()) {
          float inflation = mFrame->GetFontSizeInflation();
          mFontMetrics =
              nsLayoutUtils::GetFontMetricsForFrame(mFrame, inflation);
          mFrame->SetInflatedFontMetrics(mFontMetrics);
        } else {
          mFontMetrics = mFrame->InflatedFontMetrics();
        }
      } else {
        mFontMetrics = nsLayoutUtils::GetFontMetricsForFrame(mFrame, 1.0f);
      }
    }
    mFontGroup = mFontMetrics->GetThebesFontGroup();
  }

  const RefPtr<gfxTextRun> mTextRun;
  mutable gfxFontGroup* mFontGroup;
  mutable RefPtr<nsFontMetrics> mFontMetrics;
  const nsStyleText* mTextStyle;
  const nsTextFragment* mFrag;
  const nsIFrame* mLineContainer;
  nsTextFrame* mFrame;
  gfxSkipCharsIterator mStart;  // Offset in original and transformed string
  const gfxSkipCharsIterator mTempIterator;

  // Either null, or pointing to the frame's TabWidthProperty.
  mutable TabWidthStore* mTabWidths;
  // How far we've done tab-width calculation; this is ONLY valid when
  // mTabWidths is nullptr (otherwise rely on mTabWidths->mLimit instead).
  // It's a DOM offset relative to the current frame's offset.
  mutable uint32_t mTabWidthsAnalyzedLimit;

  int32_t mLength;                  // DOM string length, may be INT32_MAX
  const gfxFloat mWordSpacing;      // space for each whitespace char
  const gfxFloat mLetterSpacing;    // space for each letter
  mutable gfxFloat mMinTabAdvance;  // min advance for <tab> char
  mutable gfxFloat mHyphenWidth;
  mutable gfxFloat mOffsetFromBlockOriginForTabs;

  // The values in mJustificationSpacings corresponds to unskipped
  // characters start from mJustificationArrayStart.
  uint32_t mJustificationArrayStart;
  nsTArray<Spacing> mJustificationSpacings;

  const bool mReflowing;
  const nsTextFrame::TextRunType mWhichTextRun;
};

/**
 * Finds the offset of the first character of the cluster containing aPos
 */
static void FindClusterStart(const gfxTextRun* aTextRun, int32_t aOriginalStart,
                             gfxSkipCharsIterator* aPos) {
  while (aPos->GetOriginalOffset() > aOriginalStart) {
    if (aPos->IsOriginalCharSkipped() ||
        aTextRun->IsClusterStart(aPos->GetSkippedOffset())) {
      break;
    }
    aPos->AdvanceOriginal(-1);
  }
}

/**
 * Finds the offset of the last character of the cluster containing aPos.
 * If aAllowSplitLigature is false, we also check for a ligature-group
 * start.
 */
static void FindClusterEnd(const gfxTextRun* aTextRun, int32_t aOriginalEnd,
                           gfxSkipCharsIterator* aPos,
                           bool aAllowSplitLigature = true) {
  MOZ_ASSERT(aPos->GetOriginalOffset() < aOriginalEnd,
             "character outside string");

  aPos->AdvanceOriginal(1);
  while (aPos->GetOriginalOffset() < aOriginalEnd) {
    if (aPos->IsOriginalCharSkipped() ||
        (aTextRun->IsClusterStart(aPos->GetSkippedOffset()) &&
         (aAllowSplitLigature ||
          aTextRun->IsLigatureGroupStart(aPos->GetSkippedOffset())))) {
      break;
    }
    aPos->AdvanceOriginal(1);
  }
  aPos->AdvanceOriginal(-1);
}

JustificationInfo PropertyProvider::ComputeJustification(
    Range aRange, nsTArray<JustificationAssignment>* aAssignments) {
  JustificationInfo info;

  // Horizontal-in-vertical frame is orthogonal to the line, so it
  // doesn't actually include any justification opportunity inside.
  // The spec says such frame should be treated as a U+FFFC. Since we
  // do not insert justification opportunities on the sides of that
  // character, the sides of this frame are not justifiable either.
  if (mFrame->Style()->IsTextCombined()) {
    return info;
  }

  bool isCJ = IsChineseOrJapanese(mFrame);
  nsSkipCharsRunIterator run(
      mStart, nsSkipCharsRunIterator::LENGTH_INCLUDES_SKIPPED, aRange.Length());
  run.SetOriginalOffset(aRange.start);
  mJustificationArrayStart = run.GetSkippedOffset();

  nsTArray<JustificationAssignment> assignments;
  assignments.SetCapacity(aRange.Length());
  while (run.NextRun()) {
    uint32_t originalOffset = run.GetOriginalOffset();
    uint32_t skippedOffset = run.GetSkippedOffset();
    uint32_t length = run.GetRunLength();
    assignments.SetLength(skippedOffset + length - mJustificationArrayStart);

    gfxSkipCharsIterator iter = run.GetPos();
    for (uint32_t i = 0; i < length; ++i) {
      uint32_t offset = originalOffset + i;
      if (!IsJustifiableCharacter(mTextStyle, mFrag, offset, isCJ)) {
        continue;
      }

      iter.SetOriginalOffset(offset);

      FindClusterStart(mTextRun, originalOffset, &iter);
      uint32_t firstCharOffset = iter.GetSkippedOffset();
      uint32_t firstChar = firstCharOffset > mJustificationArrayStart
                               ? firstCharOffset - mJustificationArrayStart
                               : 0;
      if (!firstChar) {
        info.mIsStartJustifiable = true;
      } else {
        auto& assign = assignments[firstChar];
        auto& prevAssign = assignments[firstChar - 1];
        if (prevAssign.mGapsAtEnd) {
          prevAssign.mGapsAtEnd = 1;
          assign.mGapsAtStart = 1;
        } else {
          assign.mGapsAtStart = 2;
          info.mInnerOpportunities++;
        }
      }

      FindClusterEnd(mTextRun, originalOffset + length, &iter);
      uint32_t lastChar = iter.GetSkippedOffset() - mJustificationArrayStart;
      // Assign the two gaps temporary to the last char. If the next cluster is
      // justifiable as well, one of the gaps will be removed by code above.
      assignments[lastChar].mGapsAtEnd = 2;
      info.mInnerOpportunities++;

      // Skip the whole cluster
      i = iter.GetOriginalOffset() - originalOffset;
    }
  }

  if (!assignments.IsEmpty() && assignments.LastElement().mGapsAtEnd) {
    // We counted the expansion opportunity after the last character,
    // but it is not an inner opportunity.
    MOZ_ASSERT(info.mInnerOpportunities > 0);
    info.mInnerOpportunities--;
    info.mIsEndJustifiable = true;
  }

  if (aAssignments) {
    *aAssignments = std::move(assignments);
  }
  return info;
}

// aStart, aLength in transformed string offsets
void PropertyProvider::GetSpacing(Range aRange, Spacing* aSpacing) const {
  GetSpacingInternal(
      aRange, aSpacing,
      !(mTextRun->GetFlags2() & nsTextFrameUtils::Flags::TEXT_HAS_TAB));
}

static bool CanAddSpacingAfter(const gfxTextRun* aTextRun, uint32_t aOffset) {
  if (aOffset + 1 >= aTextRun->GetLength()) return true;
  return aTextRun->IsClusterStart(aOffset + 1) &&
         aTextRun->IsLigatureGroupStart(aOffset + 1) &&
         !aTextRun->CharIsFormattingControl(aOffset);
}

static gfxFloat ComputeTabWidthAppUnits(const nsIFrame* aFrame,
                                        gfxTextRun* aTextRun) {
  const nsStyleText* textStyle = aFrame->StyleText();
  if (textStyle->mTabSize.GetUnit() != eStyleUnit_Factor) {
    nscoord w = textStyle->mTabSize.GetCoordValue();
    MOZ_ASSERT(w >= 0);
    return w;
  }

  gfxFloat spaces = textStyle->mTabSize.GetFactorValue();
  MOZ_ASSERT(spaces >= 0);

  // Round the space width when converting to appunits the same way
  // textruns do.
  gfxFloat spaceWidthAppUnits = NS_round(
      GetFirstFontMetrics(aTextRun->GetFontGroup(), aTextRun->IsVertical())
          .spaceWidth *
      aTextRun->GetAppUnitsPerDevUnit());
  return spaces * spaceWidthAppUnits;
}

void PropertyProvider::GetSpacingInternal(Range aRange, Spacing* aSpacing,
                                          bool aIgnoreTabs) const {
  MOZ_ASSERT(IsInBounds(mStart, mLength, aRange), "Range out of bounds");

  uint32_t index;
  for (index = 0; index < aRange.Length(); ++index) {
    aSpacing[index].mBefore = 0.0;
    aSpacing[index].mAfter = 0.0;
  }

  if (mFrame->Style()->IsTextCombined()) {
    return;
  }

  // Find our offset into the original+transformed string
  gfxSkipCharsIterator start(mStart);
  start.SetSkippedOffset(aRange.start);

  // First, compute the word and letter spacing
  if (mWordSpacing || mLetterSpacing) {
    // Iterate over non-skipped characters
    nsSkipCharsRunIterator run(
        start, nsSkipCharsRunIterator::LENGTH_UNSKIPPED_ONLY, aRange.Length());
    while (run.NextRun()) {
      uint32_t runOffsetInSubstring = run.GetSkippedOffset() - aRange.start;
      gfxSkipCharsIterator iter = run.GetPos();
      for (int32_t i = 0; i < run.GetRunLength(); ++i) {
        if (CanAddSpacingAfter(mTextRun, run.GetSkippedOffset() + i)) {
          // End of a cluster, not in a ligature: put letter-spacing after it
          aSpacing[runOffsetInSubstring + i].mAfter += mLetterSpacing;
        }
        if (IsCSSWordSpacingSpace(mFrag, i + run.GetOriginalOffset(), mFrame,
                                  mTextStyle)) {
          // It kinda sucks, but space characters can be part of clusters,
          // and even still be whitespace (I think!)
          iter.SetSkippedOffset(run.GetSkippedOffset() + i);
          FindClusterEnd(mTextRun, run.GetOriginalOffset() + run.GetRunLength(),
                         &iter);
          uint32_t runOffset = iter.GetSkippedOffset() - aRange.start;
          aSpacing[runOffset].mAfter += mWordSpacing;
        }
      }
    }
  }

  // Now add tab spacing, if there is any
  if (!aIgnoreTabs) {
    gfxFloat tabWidth = ComputeTabWidthAppUnits(mFrame, mTextRun);
    if (tabWidth > 0) {
      CalcTabWidths(aRange, tabWidth);
      if (mTabWidths) {
        mTabWidths->ApplySpacing(aSpacing,
                                 aRange.start - mStart.GetSkippedOffset(),
                                 aRange.Length());
      }
    }
  }

  // Now add in justification spacing
  if (mJustificationSpacings.Length() > 0) {
    // If there is any spaces trimmed at the end, aStart + aLength may
    // be larger than the flags array. When that happens, we can simply
    // ignore those spaces.
    auto arrayEnd = mJustificationArrayStart +
                    static_cast<uint32_t>(mJustificationSpacings.Length());
    auto end = std::min(aRange.end, arrayEnd);
    MOZ_ASSERT(aRange.start >= mJustificationArrayStart);
    for (auto i = aRange.start; i < end; i++) {
      const auto& spacing =
          mJustificationSpacings[i - mJustificationArrayStart];
      uint32_t offset = i - aRange.start;
      aSpacing[offset].mBefore += spacing.mBefore;
      aSpacing[offset].mAfter += spacing.mAfter;
    }
  }
}

// aX and the result are in whole appunits.
static gfxFloat AdvanceToNextTab(gfxFloat aX, gfxFloat aTabWidth,
                                 gfxFloat aMinAdvance) {
  // Advance aX to the next multiple of aTabWidth. We must advance
  // by at least aMinAdvance.
  return ceil((aX + aMinAdvance) / aTabWidth) * aTabWidth;
}

void PropertyProvider::CalcTabWidths(Range aRange, gfxFloat aTabWidth) const {
  MOZ_ASSERT(aTabWidth > 0);

  if (!mTabWidths) {
    if (mReflowing && !mLineContainer) {
      // Intrinsic width computation does its own tab processing. We
      // just don't do anything here.
      return;
    }
    if (!mReflowing) {
      mTabWidths = mFrame->GetProperty(TabWidthProperty());
#ifdef DEBUG
      // If we're not reflowing, we should have already computed the
      // tab widths; check that they're available as far as the last
      // tab character present (if any)
      for (uint32_t i = aRange.end; i > aRange.start; --i) {
        if (mTextRun->CharIsTab(i - 1)) {
          uint32_t startOffset = mStart.GetSkippedOffset();
          NS_ASSERTION(mTabWidths && mTabWidths->mLimit + startOffset >= i,
                       "Precomputed tab widths are missing!");
          break;
        }
      }
#endif
      return;
    }
  }

  uint32_t startOffset = mStart.GetSkippedOffset();
  MOZ_ASSERT(aRange.start >= startOffset, "wrong start offset");
  MOZ_ASSERT(aRange.end <= startOffset + mLength, "beyond the end");
  uint32_t tabsEnd =
      (mTabWidths ? mTabWidths->mLimit : mTabWidthsAnalyzedLimit) + startOffset;
  if (tabsEnd < aRange.end) {
    NS_ASSERTION(mReflowing,
                 "We need precomputed tab widths, but don't have enough.");

    for (uint32_t i = tabsEnd; i < aRange.end; ++i) {
      Spacing spacing;
      GetSpacingInternal(Range(i, i + 1), &spacing, true);
      mOffsetFromBlockOriginForTabs += spacing.mBefore;

      if (!mTextRun->CharIsTab(i)) {
        if (mTextRun->IsClusterStart(i)) {
          uint32_t clusterEnd = i + 1;
          while (clusterEnd < mTextRun->GetLength() &&
                 !mTextRun->IsClusterStart(clusterEnd)) {
            ++clusterEnd;
          }
          mOffsetFromBlockOriginForTabs +=
              mTextRun->GetAdvanceWidth(Range(i, clusterEnd), nullptr);
        }
      } else {
        if (!mTabWidths) {
          mTabWidths = new TabWidthStore(mFrame->GetContentOffset());
          mFrame->SetProperty(TabWidthProperty(), mTabWidths);
        }
        double nextTab = AdvanceToNextTab(mOffsetFromBlockOriginForTabs,
                                          aTabWidth, MinTabAdvance());
        mTabWidths->mWidths.AppendElement(
            TabWidth(i - startOffset,
                     NSToIntRound(nextTab - mOffsetFromBlockOriginForTabs)));
        mOffsetFromBlockOriginForTabs = nextTab;
      }

      mOffsetFromBlockOriginForTabs += spacing.mAfter;
    }

    if (mTabWidths) {
      mTabWidths->mLimit = aRange.end - startOffset;
    }
  }

  if (!mTabWidths) {
    // Delete any stale property that may be left on the frame
    mFrame->DeleteProperty(TabWidthProperty());
    mTabWidthsAnalyzedLimit =
        std::max(mTabWidthsAnalyzedLimit, aRange.end - startOffset);
  }
}

gfxFloat PropertyProvider::GetHyphenWidth() const {
  if (mHyphenWidth < 0) {
    mHyphenWidth = GetFontGroup()->GetHyphenWidth(this);
  }
  return mHyphenWidth + mLetterSpacing;
}

static inline bool IS_HYPHEN(char16_t u) {
  return u == char16_t('-') ||  // HYPHEN-MINUS
         u == 0x058A ||         // ARMENIAN HYPHEN
         u == 0x2010 ||         // HYPHEN
         u == 0x2012 ||         // FIGURE DASH
         u == 0x2013;           // EN DASH
}

void PropertyProvider::GetHyphenationBreaks(Range aRange,
                                            HyphenType* aBreakBefore) const {
  MOZ_ASSERT(IsInBounds(mStart, mLength, aRange), "Range out of bounds");
  MOZ_ASSERT(mLength != INT32_MAX, "Can't call this with undefined length");

  if (!mTextStyle->WhiteSpaceCanWrap(mFrame) ||
      mTextStyle->mHyphens == StyleHyphens::None) {
    memset(aBreakBefore, static_cast<uint8_t>(HyphenType::None),
           aRange.Length() * sizeof(HyphenType));
    return;
  }

  // Iterate through the original-string character runs
  nsSkipCharsRunIterator run(
      mStart, nsSkipCharsRunIterator::LENGTH_UNSKIPPED_ONLY, aRange.Length());
  run.SetSkippedOffset(aRange.start);
  // We need to visit skipped characters so that we can detect SHY
  run.SetVisitSkipped();

  int32_t prevTrailingCharOffset = run.GetPos().GetOriginalOffset() - 1;
  bool allowHyphenBreakBeforeNextChar =
      prevTrailingCharOffset >= mStart.GetOriginalOffset() &&
      prevTrailingCharOffset < mStart.GetOriginalOffset() + mLength &&
      mFrag->CharAt(prevTrailingCharOffset) == CH_SHY;

  while (run.NextRun()) {
    NS_ASSERTION(run.GetRunLength() > 0, "Shouldn't return zero-length runs");
    if (run.IsSkipped()) {
      // Check if there's a soft hyphen which would let us hyphenate before
      // the next non-skipped character. Don't look at soft hyphens followed
      // by other skipped characters, we won't use them.
      allowHyphenBreakBeforeNextChar =
          mFrag->CharAt(run.GetOriginalOffset() + run.GetRunLength() - 1) ==
          CH_SHY;
    } else {
      int32_t runOffsetInSubstring = run.GetSkippedOffset() - aRange.start;
      memset(aBreakBefore + runOffsetInSubstring,
             static_cast<uint8_t>(HyphenType::None),
             run.GetRunLength() * sizeof(HyphenType));
      // Don't allow hyphen breaks at the start of the line
      aBreakBefore[runOffsetInSubstring] =
          allowHyphenBreakBeforeNextChar &&
                  (!(mFrame->GetStateBits() & TEXT_START_OF_LINE) ||
                   run.GetSkippedOffset() > mStart.GetSkippedOffset())
              ? HyphenType::Soft
              : HyphenType::None;
      allowHyphenBreakBeforeNextChar = false;
    }
  }

  if (mTextStyle->mHyphens == StyleHyphens::Auto) {
    gfxSkipCharsIterator skipIter(mStart);
    for (uint32_t i = 0; i < aRange.Length(); ++i) {
      if (IS_HYPHEN(mFrag->CharAt(
              skipIter.ConvertSkippedToOriginal(aRange.start + i)))) {
        if (i < aRange.Length() - 1) {
          aBreakBefore[i + 1] = HyphenType::Explicit;
        }
        continue;
      }

      if (mTextRun->CanHyphenateBefore(aRange.start + i) &&
          aBreakBefore[i] == HyphenType::None) {
        aBreakBefore[i] = HyphenType::AutoWithoutManualInSameWord;
      }
    }
  }
}

void PropertyProvider::InitializeForDisplay(bool aTrimAfter) {
  nsTextFrame::TrimmedOffsets trimmed =
      mFrame->GetTrimmedOffsets(mFrag, aTrimAfter);
  mStart.SetOriginalOffset(trimmed.mStart);
  mLength = trimmed.mLength;
  SetupJustificationSpacing(true);
}

void PropertyProvider::InitializeForMeasure() {
  nsTextFrame::TrimmedOffsets trimmed =
      mFrame->GetTrimmedOffsets(mFrag, true, false);
  mStart.SetOriginalOffset(trimmed.mStart);
  mLength = trimmed.mLength;
  SetupJustificationSpacing(false);
}

void PropertyProvider::SetupJustificationSpacing(bool aPostReflow) {
  MOZ_ASSERT(mLength != INT32_MAX, "Can't call this with undefined length");

  if (!(mFrame->GetStateBits() & TEXT_JUSTIFICATION_ENABLED)) {
    return;
  }

  gfxSkipCharsIterator start(mStart), end(mStart);
  // We can't just use our mLength here; when InitializeForDisplay is
  // called with false for aTrimAfter, we still shouldn't be assigning
  // justification space to any trailing whitespace.
  nsTextFrame::TrimmedOffsets trimmed =
      mFrame->GetTrimmedOffsets(mFrag, true, aPostReflow);
  end.AdvanceOriginal(trimmed.mLength);
  gfxSkipCharsIterator realEnd(end);

  Range range(uint32_t(start.GetOriginalOffset()),
              uint32_t(end.GetOriginalOffset()));
  nsTArray<JustificationAssignment> assignments;
  JustificationInfo info = ComputeJustification(range, &assignments);

  auto assign = mFrame->GetJustificationAssignment();
  auto totalGaps = JustificationUtils::CountGaps(info, assign);
  if (!totalGaps || assignments.IsEmpty()) {
    // Nothing to do, nothing is justifiable and we shouldn't have any
    // justification space assigned
    return;
  }

  // Remember that textrun measurements are in the run's orientation,
  // so its advance "width" is actually a height in vertical writing modes,
  // corresponding to the inline-direction of the frame.
  gfxFloat naturalWidth = mTextRun->GetAdvanceWidth(
      Range(mStart.GetSkippedOffset(), realEnd.GetSkippedOffset()), this);
  if (mFrame->GetStateBits() & TEXT_HYPHEN_BREAK) {
    naturalWidth += GetHyphenWidth();
  }
  nscoord totalSpacing = mFrame->ISize() - naturalWidth;
  if (totalSpacing <= 0) {
    // No space available
    return;
  }

  assignments[0].mGapsAtStart = assign.mGapsAtStart;
  assignments.LastElement().mGapsAtEnd = assign.mGapsAtEnd;

  MOZ_ASSERT(mJustificationSpacings.IsEmpty());
  JustificationApplicationState state(totalGaps, totalSpacing);
  mJustificationSpacings.SetCapacity(assignments.Length());
  for (const JustificationAssignment& assign : assignments) {
    Spacing* spacing = mJustificationSpacings.AppendElement();
    spacing->mBefore = state.Consume(assign.mGapsAtStart);
    spacing->mAfter = state.Consume(assign.mGapsAtEnd);
  }
}

//----------------------------------------------------------------------

static nscolor EnsureDifferentColors(nscolor colorA, nscolor colorB) {
  if (colorA == colorB) {
    nscolor res;
    res = NS_RGB(NS_GET_R(colorA) ^ 0xff, NS_GET_G(colorA) ^ 0xff,
                 NS_GET_B(colorA) ^ 0xff);
    return res;
  }
  return colorA;
}

//-----------------------------------------------------------------------------

nsTextPaintStyle::nsTextPaintStyle(nsTextFrame* aFrame)
    : mFrame(aFrame),
      mPresContext(aFrame->PresContext()),
      mInitCommonColors(false),
      mInitSelectionColorsAndShadow(false),
      mResolveColors(true),
      mSelectionTextColor(NS_RGBA(0, 0, 0, 0)),
      mSelectionBGColor(NS_RGBA(0, 0, 0, 0)),
      mHasSelectionShadow(false),
      mSufficientContrast(0),
      mFrameBackgroundColor(NS_RGBA(0, 0, 0, 0)),
      mSystemFieldForegroundColor(NS_RGBA(0, 0, 0, 0)),
      mSystemFieldBackgroundColor(NS_RGBA(0, 0, 0, 0)) {
  for (uint32_t i = 0; i < ArrayLength(mSelectionStyle); i++)
    mSelectionStyle[i].mInit = false;
}

bool nsTextPaintStyle::EnsureSufficientContrast(nscolor* aForeColor,
                                                nscolor* aBackColor) {
  InitCommonColors();

  // If the combination of selection background color and frame background color
  // is sufficient contrast, don't exchange the selection colors.
  int32_t backLuminosityDifference =
      NS_LUMINOSITY_DIFFERENCE(*aBackColor, mFrameBackgroundColor);
  if (backLuminosityDifference >= mSufficientContrast) return false;

  // Otherwise, we should use the higher-contrast color for the selection
  // background color.
  int32_t foreLuminosityDifference =
      NS_LUMINOSITY_DIFFERENCE(*aForeColor, mFrameBackgroundColor);
  if (backLuminosityDifference < foreLuminosityDifference) {
    nscolor tmpColor = *aForeColor;
    *aForeColor = *aBackColor;
    *aBackColor = tmpColor;
    return true;
  }
  return false;
}

nscolor nsTextPaintStyle::GetTextColor() {
  if (nsSVGUtils::IsInSVGTextSubtree(mFrame)) {
    if (!mResolveColors) return NS_SAME_AS_FOREGROUND_COLOR;

    const nsStyleSVG* style = mFrame->StyleSVG();
    switch (style->mFill.Type()) {
      case eStyleSVGPaintType_None:
        return NS_RGBA(0, 0, 0, 0);
      case eStyleSVGPaintType_Color:
        return nsLayoutUtils::GetColor(mFrame, &nsStyleSVG::mFill);
      default:
        NS_ERROR("cannot resolve SVG paint to nscolor");
        return NS_RGBA(0, 0, 0, 255);
    }
  }

  return nsLayoutUtils::GetColor(mFrame, &nsStyleText::mWebkitTextFillColor);
}

bool nsTextPaintStyle::GetSelectionColors(nscolor* aForeColor,
                                          nscolor* aBackColor) {
  NS_ASSERTION(aForeColor, "aForeColor is null");
  NS_ASSERTION(aBackColor, "aBackColor is null");

  if (!InitSelectionColorsAndShadow()) return false;

  *aForeColor = mSelectionTextColor;
  *aBackColor = mSelectionBGColor;
  return true;
}

void nsTextPaintStyle::GetHighlightColors(nscolor* aForeColor,
                                          nscolor* aBackColor) {
  NS_ASSERTION(aForeColor, "aForeColor is null");
  NS_ASSERTION(aBackColor, "aBackColor is null");

  const nsFrameSelection* frameSelection = mFrame->GetConstFrameSelection();
  const Selection* selection =
      frameSelection->GetSelection(SelectionType::eFind);
  const SelectionCustomColors* customColors = nullptr;
  if (selection) {
    customColors = selection->GetCustomColors();
  }

  if (!customColors) {
    nscolor backColor =
        LookAndFeel::GetColor(LookAndFeel::eColorID_TextHighlightBackground);
    nscolor foreColor =
        LookAndFeel::GetColor(LookAndFeel::eColorID_TextHighlightForeground);
    EnsureSufficientContrast(&foreColor, &backColor);
    *aForeColor = foreColor;
    *aBackColor = backColor;

    return;
  }

  if (customColors->mForegroundColor && customColors->mBackgroundColor) {
    nscolor foreColor = *customColors->mForegroundColor;
    nscolor backColor = *customColors->mBackgroundColor;

    if (EnsureSufficientContrast(&foreColor, &backColor) &&
        customColors->mAltForegroundColor &&
        customColors->mAltBackgroundColor) {
      foreColor = *customColors->mAltForegroundColor;
      backColor = *customColors->mAltBackgroundColor;
    }

    *aForeColor = foreColor;
    *aBackColor = backColor;
    return;
  }

  InitCommonColors();

  if (customColors->mBackgroundColor) {
    // !mForegroundColor means "currentColor"; the current color of the text.
    nscolor foreColor = GetTextColor();
    nscolor backColor = *customColors->mBackgroundColor;

    int32_t luminosityDifference =
        NS_LUMINOSITY_DIFFERENCE(foreColor, backColor);

    if (mSufficientContrast > luminosityDifference &&
        customColors->mAltBackgroundColor) {
      int32_t altLuminosityDifference = NS_LUMINOSITY_DIFFERENCE(
          foreColor, *customColors->mAltBackgroundColor);

      if (luminosityDifference < altLuminosityDifference) {
        backColor = *customColors->mAltBackgroundColor;
      }
    }

    *aForeColor = foreColor;
    *aBackColor = backColor;
    return;
  }

  if (customColors->mForegroundColor) {
    nscolor foreColor = *customColors->mForegroundColor;
    // !mBackgroundColor means "transparent"; the current color of the
    // background.

    int32_t luminosityDifference =
        NS_LUMINOSITY_DIFFERENCE(foreColor, mFrameBackgroundColor);

    if (mSufficientContrast > luminosityDifference &&
        customColors->mAltForegroundColor) {
      int32_t altLuminosityDifference = NS_LUMINOSITY_DIFFERENCE(
          *customColors->mForegroundColor, mFrameBackgroundColor);

      if (luminosityDifference < altLuminosityDifference) {
        foreColor = *customColors->mAltForegroundColor;
      }
    }

    *aForeColor = foreColor;
    *aBackColor = NS_TRANSPARENT;
    return;
  }

  // There are neither mForegroundColor nor mBackgroundColor.
  *aForeColor = GetTextColor();
  *aBackColor = NS_TRANSPARENT;
}

void nsTextPaintStyle::GetURLSecondaryColor(nscolor* aForeColor) {
  NS_ASSERTION(aForeColor, "aForeColor is null");

  nscolor textColor = GetTextColor();
  textColor = NS_RGBA(NS_GET_R(textColor), NS_GET_G(textColor),
                      NS_GET_B(textColor), (uint8_t)(255 * 0.5f));
  // Don't use true alpha color for readability.
  InitCommonColors();
  *aForeColor = NS_ComposeColors(mFrameBackgroundColor, textColor);
}

void nsTextPaintStyle::GetIMESelectionColors(int32_t aIndex,
                                             nscolor* aForeColor,
                                             nscolor* aBackColor) {
  NS_ASSERTION(aForeColor, "aForeColor is null");
  NS_ASSERTION(aBackColor, "aBackColor is null");
  NS_ASSERTION(aIndex >= 0 && aIndex < 5, "Index out of range");

  nsSelectionStyle* selectionStyle = GetSelectionStyle(aIndex);
  *aForeColor = selectionStyle->mTextColor;
  *aBackColor = selectionStyle->mBGColor;
}

bool nsTextPaintStyle::GetSelectionUnderlineForPaint(int32_t aIndex,
                                                     nscolor* aLineColor,
                                                     float* aRelativeSize,
                                                     uint8_t* aStyle) {
  NS_ASSERTION(aLineColor, "aLineColor is null");
  NS_ASSERTION(aRelativeSize, "aRelativeSize is null");
  NS_ASSERTION(aIndex >= 0 && aIndex < 5, "Index out of range");

  nsSelectionStyle* selectionStyle = GetSelectionStyle(aIndex);
  if (selectionStyle->mUnderlineStyle == NS_STYLE_TEXT_DECORATION_STYLE_NONE ||
      selectionStyle->mUnderlineColor == NS_TRANSPARENT ||
      selectionStyle->mUnderlineRelativeSize <= 0.0f)
    return false;

  *aLineColor = selectionStyle->mUnderlineColor;
  *aRelativeSize = selectionStyle->mUnderlineRelativeSize;
  *aStyle = selectionStyle->mUnderlineStyle;
  return true;
}

void nsTextPaintStyle::InitCommonColors() {
  if (mInitCommonColors) return;

  nsIFrame* bgFrame = nsCSSRendering::FindNonTransparentBackgroundFrame(mFrame);
  NS_ASSERTION(bgFrame, "Cannot find NonTransparentBackgroundFrame.");
  nscolor bgColor =
      bgFrame->GetVisitedDependentColor(&nsStyleBackground::mBackgroundColor);

  nscolor defaultBgColor = mPresContext->DefaultBackgroundColor();
  mFrameBackgroundColor = NS_ComposeColors(defaultBgColor, bgColor);

  mSystemFieldForegroundColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID__moz_fieldtext);
  mSystemFieldBackgroundColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID__moz_field);

  if (bgFrame->IsThemed()) {
    // Assume a native widget has sufficient contrast always
    mSufficientContrast = 0;
    mInitCommonColors = true;
    return;
  }

  NS_ASSERTION(NS_GET_A(defaultBgColor) == 255,
               "default background color is not opaque");

  nscolor defaultWindowBackgroundColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID_WindowBackground);
  nscolor selectionTextColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID_TextSelectForeground);
  nscolor selectionBGColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID_TextSelectBackground);

  mSufficientContrast = std::min(
      std::min(NS_SUFFICIENT_LUMINOSITY_DIFFERENCE,
               NS_LUMINOSITY_DIFFERENCE(selectionTextColor, selectionBGColor)),
      NS_LUMINOSITY_DIFFERENCE(defaultWindowBackgroundColor, selectionBGColor));

  mInitCommonColors = true;
}

nscolor nsTextPaintStyle::GetSystemFieldForegroundColor() {
  InitCommonColors();
  return mSystemFieldForegroundColor;
}

nscolor nsTextPaintStyle::GetSystemFieldBackgroundColor() {
  InitCommonColors();
  return mSystemFieldBackgroundColor;
}

bool nsTextPaintStyle::InitSelectionColorsAndShadow() {
  if (mInitSelectionColorsAndShadow) return true;

  int16_t selectionFlags;
  int16_t selectionStatus = mFrame->GetSelectionStatus(&selectionFlags);
  if (!(selectionFlags & nsISelectionDisplay::DISPLAY_TEXT) ||
      selectionStatus < nsISelectionController::SELECTION_ON) {
    // Not displaying the normal selection.
    // We're not caching this fact, so every call to GetSelectionColors
    // will come through here. We could avoid this, but it's not really worth
    // it.
    return false;
  }

  mInitSelectionColorsAndShadow = true;

  if (selectionStatus == nsISelectionController::SELECTION_ON) {
    // Use ::selection pseudo class.
    if (RefPtr<ComputedStyle> style = mFrame->ComputeSelectionStyle()) {
      mSelectionBGColor =
          style->GetVisitedDependentColor(&nsStyleBackground::mBackgroundColor);
      mSelectionTextColor =
          style->GetVisitedDependentColor(&nsStyleText::mWebkitTextFillColor);
      mHasSelectionShadow = true;
      mSelectionShadow = style->StyleText()->mTextShadow;
      return true;
    }
  }

  nscolor selectionBGColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID_TextSelectBackground);

  if (selectionStatus == nsISelectionController::SELECTION_ATTENTION) {
    mSelectionBGColor = LookAndFeel::GetColor(
        LookAndFeel::eColorID_TextSelectBackgroundAttention);
    mSelectionBGColor =
        EnsureDifferentColors(mSelectionBGColor, selectionBGColor);
  } else if (selectionStatus != nsISelectionController::SELECTION_ON) {
    mSelectionBGColor = LookAndFeel::GetColor(
        LookAndFeel::eColorID_TextSelectBackgroundDisabled);
    mSelectionBGColor =
        EnsureDifferentColors(mSelectionBGColor, selectionBGColor);
  } else {
    mSelectionBGColor = selectionBGColor;
  }

  mSelectionTextColor =
      LookAndFeel::GetColor(LookAndFeel::eColorID_TextSelectForeground);

  if (mResolveColors) {
    // On MacOS X, only the background color gets set,
    // the text color remains intact.
    if (mSelectionTextColor == NS_DONT_CHANGE_COLOR) {
      nscolor frameColor =
          nsSVGUtils::IsInSVGTextSubtree(mFrame)
              ? mFrame->GetVisitedDependentColor(&nsStyleSVG::mFill)
              : mFrame->GetVisitedDependentColor(
                    &nsStyleText::mWebkitTextFillColor);
      mSelectionTextColor =
          EnsureDifferentColors(frameColor, mSelectionBGColor);
    } else if (mSelectionTextColor == NS_CHANGE_COLOR_IF_SAME_AS_BG) {
      nscolor frameColor =
          nsSVGUtils::IsInSVGTextSubtree(mFrame)
              ? mFrame->GetVisitedDependentColor(&nsStyleSVG::mFill)
              : mFrame->GetVisitedDependentColor(
                    &nsStyleText::mWebkitTextFillColor);
      if (frameColor == mSelectionBGColor) {
        mSelectionTextColor = LookAndFeel::GetColor(
            LookAndFeel::eColorID_TextSelectForegroundCustom);
      }
    } else {
      EnsureSufficientContrast(&mSelectionTextColor, &mSelectionBGColor);
    }
  } else {
    if (mSelectionTextColor == NS_DONT_CHANGE_COLOR) {
      mSelectionTextColor = NS_SAME_AS_FOREGROUND_COLOR;
    }
  }
  return true;
}

nsTextPaintStyle::nsSelectionStyle* nsTextPaintStyle::GetSelectionStyle(
    int32_t aIndex) {
  InitSelectionStyle(aIndex);
  return &mSelectionStyle[aIndex];
}

struct StyleIDs {
  LookAndFeel::ColorID mForeground, mBackground, mLine;
  LookAndFeel::IntID mLineStyle;
  LookAndFeel::FloatID mLineRelativeSize;
};
static StyleIDs SelectionStyleIDs[] = {
    {LookAndFeel::eColorID_IMERawInputForeground,
     LookAndFeel::eColorID_IMERawInputBackground,
     LookAndFeel::eColorID_IMERawInputUnderline,
     LookAndFeel::eIntID_IMERawInputUnderlineStyle,
     LookAndFeel::eFloatID_IMEUnderlineRelativeSize},
    {LookAndFeel::eColorID_IMESelectedRawTextForeground,
     LookAndFeel::eColorID_IMESelectedRawTextBackground,
     LookAndFeel::eColorID_IMESelectedRawTextUnderline,
     LookAndFeel::eIntID_IMESelectedRawTextUnderlineStyle,
     LookAndFeel::eFloatID_IMEUnderlineRelativeSize},
    {LookAndFeel::eColorID_IMEConvertedTextForeground,
     LookAndFeel::eColorID_IMEConvertedTextBackground,
     LookAndFeel::eColorID_IMEConvertedTextUnderline,
     LookAndFeel::eIntID_IMEConvertedTextUnderlineStyle,
     LookAndFeel::eFloatID_IMEUnderlineRelativeSize},
    {LookAndFeel::eColorID_IMESelectedConvertedTextForeground,
     LookAndFeel::eColorID_IMESelectedConvertedTextBackground,
     LookAndFeel::eColorID_IMESelectedConvertedTextUnderline,
     LookAndFeel::eIntID_IMESelectedConvertedTextUnderline,
     LookAndFeel::eFloatID_IMEUnderlineRelativeSize},
    {LookAndFeel::eColorID_LAST_COLOR, LookAndFeel::eColorID_LAST_COLOR,
     LookAndFeel::eColorID_SpellCheckerUnderline,
     LookAndFeel::eIntID_SpellCheckerUnderlineStyle,
     LookAndFeel::eFloatID_SpellCheckerUnderlineRelativeSize}};

void nsTextPaintStyle::InitSelectionStyle(int32_t aIndex) {
  NS_ASSERTION(aIndex >= 0 && aIndex < 5, "aIndex is invalid");
  nsSelectionStyle* selectionStyle = &mSelectionStyle[aIndex];
  if (selectionStyle->mInit) return;

  StyleIDs* styleIDs = &SelectionStyleIDs[aIndex];

  nscolor foreColor, backColor;
  if (styleIDs->mForeground == LookAndFeel::eColorID_LAST_COLOR) {
    foreColor = NS_SAME_AS_FOREGROUND_COLOR;
  } else {
    foreColor = LookAndFeel::GetColor(styleIDs->mForeground);
  }
  if (styleIDs->mBackground == LookAndFeel::eColorID_LAST_COLOR) {
    backColor = NS_TRANSPARENT;
  } else {
    backColor = LookAndFeel::GetColor(styleIDs->mBackground);
  }

  // Convert special color to actual color
  NS_ASSERTION(foreColor != NS_TRANSPARENT,
               "foreColor cannot be NS_TRANSPARENT");
  NS_ASSERTION(backColor != NS_SAME_AS_FOREGROUND_COLOR,
               "backColor cannot be NS_SAME_AS_FOREGROUND_COLOR");
  NS_ASSERTION(backColor != NS_40PERCENT_FOREGROUND_COLOR,
               "backColor cannot be NS_40PERCENT_FOREGROUND_COLOR");

  if (mResolveColors) {
    foreColor = GetResolvedForeColor(foreColor, GetTextColor(), backColor);

    if (NS_GET_A(backColor) > 0)
      EnsureSufficientContrast(&foreColor, &backColor);
  }

  nscolor lineColor;
  float relativeSize;
  uint8_t lineStyle;
  GetSelectionUnderline(mPresContext, aIndex, &lineColor, &relativeSize,
                        &lineStyle);

  if (mResolveColors)
    lineColor = GetResolvedForeColor(lineColor, foreColor, backColor);

  selectionStyle->mTextColor = foreColor;
  selectionStyle->mBGColor = backColor;
  selectionStyle->mUnderlineColor = lineColor;
  selectionStyle->mUnderlineStyle = lineStyle;
  selectionStyle->mUnderlineRelativeSize = relativeSize;
  selectionStyle->mInit = true;
}

/* static */ bool nsTextPaintStyle::GetSelectionUnderline(
    nsPresContext* aPresContext, int32_t aIndex, nscolor* aLineColor,
    float* aRelativeSize, uint8_t* aStyle) {
  NS_ASSERTION(aPresContext, "aPresContext is null");
  NS_ASSERTION(aRelativeSize, "aRelativeSize is null");
  NS_ASSERTION(aStyle, "aStyle is null");
  NS_ASSERTION(aIndex >= 0 && aIndex < 5, "Index out of range");

  StyleIDs& styleID = SelectionStyleIDs[aIndex];

  nscolor color = LookAndFeel::GetColor(styleID.mLine);
  int32_t style = LookAndFeel::GetInt(styleID.mLineStyle);
  if (style > NS_STYLE_TEXT_DECORATION_STYLE_MAX) {
    NS_ERROR("Invalid underline style value is specified");
    style = NS_STYLE_TEXT_DECORATION_STYLE_SOLID;
  }
  float size = LookAndFeel::GetFloat(styleID.mLineRelativeSize);

  NS_ASSERTION(size, "selection underline relative size must be larger than 0");

  if (aLineColor) {
    *aLineColor = color;
  }
  *aRelativeSize = size;
  *aStyle = style;

  return style != NS_STYLE_TEXT_DECORATION_STYLE_NONE &&
         color != NS_TRANSPARENT && size > 0.0f;
}

bool nsTextPaintStyle::GetSelectionShadow(nsCSSShadowArray** aShadow) {
  if (!InitSelectionColorsAndShadow()) {
    return false;
  }

  if (mHasSelectionShadow) {
    *aShadow = mSelectionShadow;
    return true;
  }

  return false;
}

inline nscolor Get40PercentColor(nscolor aForeColor, nscolor aBackColor) {
  nscolor foreColor = NS_RGBA(NS_GET_R(aForeColor), NS_GET_G(aForeColor),
                              NS_GET_B(aForeColor), (uint8_t)(255 * 0.4f));
  // Don't use true alpha color for readability.
  return NS_ComposeColors(aBackColor, foreColor);
}

nscolor nsTextPaintStyle::GetResolvedForeColor(nscolor aColor,
                                               nscolor aDefaultForeColor,
                                               nscolor aBackColor) {
  if (aColor == NS_SAME_AS_FOREGROUND_COLOR) return aDefaultForeColor;

  if (aColor != NS_40PERCENT_FOREGROUND_COLOR) return aColor;

  // Get actual background color
  nscolor actualBGColor = aBackColor;
  if (actualBGColor == NS_TRANSPARENT) {
    InitCommonColors();
    actualBGColor = mFrameBackgroundColor;
  }
  return Get40PercentColor(aDefaultForeColor, actualBGColor);
}

//-----------------------------------------------------------------------------

#ifdef ACCESSIBILITY
a11y::AccType nsTextFrame::AccessibleType() {
  if (IsEmpty()) {
    RenderedText text =
        GetRenderedText(0, UINT32_MAX, TextOffsetType::OFFSETS_IN_CONTENT_TEXT,
                        TrailingWhitespace::DONT_TRIM_TRAILING_WHITESPACE);
    if (text.mString.IsEmpty()) {
      return a11y::eNoType;
    }
  }

  return a11y::eTextLeafType;
}
#endif

//-----------------------------------------------------------------------------
void nsTextFrame::Init(nsIContent* aContent, nsContainerFrame* aParent,
                       nsIFrame* aPrevInFlow) {
  NS_ASSERTION(!aPrevInFlow, "Can't be a continuation!");
  MOZ_ASSERT(aContent->IsText(), "Bogus content!");

  // Remove any NewlineOffsetProperty or InFlowContentLengthProperty since they
  // might be invalid if the content was modified while there was no frame
  if (aContent->HasFlag(NS_HAS_NEWLINE_PROPERTY)) {
    aContent->DeleteProperty(nsGkAtoms::newline);
    aContent->UnsetFlags(NS_HAS_NEWLINE_PROPERTY);
  }
  if (aContent->HasFlag(NS_HAS_FLOWLENGTH_PROPERTY)) {
    aContent->DeleteProperty(nsGkAtoms::flowlength);
    aContent->UnsetFlags(NS_HAS_FLOWLENGTH_PROPERTY);
  }

  // Since our content has a frame now, this flag is no longer needed.
  aContent->UnsetFlags(NS_CREATE_FRAME_IF_NON_WHITESPACE);

  // We're not a continuing frame.
  // mContentOffset = 0; not necessary since we get zeroed out at init
  nsFrame::Init(aContent, aParent, aPrevInFlow);
}

void nsTextFrame::ClearFrameOffsetCache() {
  // See if we need to remove ourselves from the offset cache
  if (GetStateBits() & TEXT_IN_OFFSET_CACHE) {
    nsIFrame* primaryFrame = mContent->GetPrimaryFrame();
    if (primaryFrame) {
      // The primary frame might be null here.  For example,
      // nsLineBox::DeleteLineList just destroys the frames in order, which
      // means that the primary frame is already dead if we're a continuing text
      // frame, in which case, all of its properties are gone, and we don't need
      // to worry about deleting this property here.
      primaryFrame->DeleteProperty(OffsetToFrameProperty());
    }
    RemoveStateBits(TEXT_IN_OFFSET_CACHE);
  }
}

void nsTextFrame::DestroyFrom(nsIFrame* aDestructRoot,
                              PostDestroyData& aPostDestroyData) {
  ClearFrameOffsetCache();

  // We might want to clear NS_CREATE_FRAME_IF_NON_WHITESPACE or
  // NS_REFRAME_IF_WHITESPACE on mContent here, since our parent frame
  // type might be changing.  Not clear whether it's worth it.
  ClearTextRuns();
  if (mNextContinuation) {
    mNextContinuation->SetPrevInFlow(nullptr);
  }
  // Let the base class destroy the frame
  nsFrame::DestroyFrom(aDestructRoot, aPostDestroyData);
}

class nsContinuingTextFrame final : public nsTextFrame {
 public:
  NS_DECL_FRAMEARENA_HELPERS(nsContinuingTextFrame)

  friend nsIFrame* NS_NewContinuingTextFrame(nsIPresShell* aPresShell,
                                             ComputedStyle* aStyle);

  void Init(nsIContent* aContent, nsContainerFrame* aParent,
            nsIFrame* aPrevInFlow) final;

  void DestroyFrom(nsIFrame* aDestructRoot,
                   PostDestroyData& aPostDestroyData) final;

  nsTextFrame* GetPrevContinuation() const final { return mPrevContinuation; }
  void SetPrevContinuation(nsIFrame* aPrevContinuation) final {
    NS_ASSERTION(!aPrevContinuation || Type() == aPrevContinuation->Type(),
                 "setting a prev continuation with incorrect type!");
    NS_ASSERTION(
        !nsSplittableFrame::IsInPrevContinuationChain(aPrevContinuation, this),
        "creating a loop in continuation chain!");
    mPrevContinuation = static_cast<nsTextFrame*>(aPrevContinuation);
    RemoveStateBits(NS_FRAME_IS_FLUID_CONTINUATION);
  }
  nsIFrame* GetPrevInFlowVirtual() const final { return GetPrevInFlow(); }
  nsTextFrame* GetPrevInFlow() const {
    return (GetStateBits() & NS_FRAME_IS_FLUID_CONTINUATION) ? mPrevContinuation
                                                             : nullptr;
  }
  void SetPrevInFlow(nsIFrame* aPrevInFlow) final {
    NS_ASSERTION(!aPrevInFlow || Type() == aPrevInFlow->Type(),
                 "setting a prev in flow with incorrect type!");
    NS_ASSERTION(
        !nsSplittableFrame::IsInPrevContinuationChain(aPrevInFlow, this),
        "creating a loop in continuation chain!");
    mPrevContinuation = static_cast<nsTextFrame*>(aPrevInFlow);
    AddStateBits(NS_FRAME_IS_FLUID_CONTINUATION);
  }
  nsIFrame* FirstInFlow() const final;
  nsIFrame* FirstContinuation() const final;

  void AddInlineMinISize(gfxContext* aRenderingContext,
                         InlineMinISizeData* aData) final;
  void AddInlinePrefISize(gfxContext* aRenderingContext,
                          InlinePrefISizeData* aData) final;

 protected:
  explicit nsContinuingTextFrame(ComputedStyle* aStyle)
      : nsTextFrame(aStyle, kClassID) {}

  nsTextFrame* mPrevContinuation;
};

void nsContinuingTextFrame::Init(nsIContent* aContent,
                                 nsContainerFrame* aParent,
                                 nsIFrame* aPrevInFlow) {
  NS_ASSERTION(aPrevInFlow, "Must be a continuation!");
  // NOTE: bypassing nsTextFrame::Init!!!
  nsFrame::Init(aContent, aParent, aPrevInFlow);

  nsTextFrame* prev = static_cast<nsTextFrame*>(aPrevInFlow);
  nsTextFrame* nextContinuation = prev->GetNextContinuation();
  // Hook the frame into the flow
  SetPrevInFlow(aPrevInFlow);
  aPrevInFlow->SetNextInFlow(this);
  mContentOffset = prev->GetContentOffset() + prev->GetContentLengthHint();
  NS_ASSERTION(mContentOffset < int32_t(aContent->GetText()->GetLength()),
               "Creating ContinuingTextFrame, but there is no more content");
  if (prev->Style() != Style()) {
    // We're taking part of prev's text, and its style may be different
    // so clear its textrun which may no longer be valid (and don't set ours)
    prev->ClearTextRuns();
  } else {
    float inflation = prev->GetFontSizeInflation();
    SetFontSizeInflation(inflation);
    mTextRun = prev->GetTextRun(nsTextFrame::eInflated);
    if (inflation != 1.0f) {
      gfxTextRun* uninflatedTextRun =
          prev->GetTextRun(nsTextFrame::eNotInflated);
      if (uninflatedTextRun) {
        SetTextRun(uninflatedTextRun, nsTextFrame::eNotInflated, 1.0f);
      }
    }
  }
  if (aPrevInFlow->GetStateBits() & NS_FRAME_IS_BIDI) {
    FrameBidiData bidiData = aPrevInFlow->GetBidiData();
    bidiData.precedingControl = kBidiLevelNone;
    SetProperty(BidiDataProperty(), bidiData);

    if (nextContinuation) {
      SetNextContinuation(nextContinuation);
      nextContinuation->SetPrevContinuation(this);
      // Adjust next-continuations' content offset as needed.
      while (nextContinuation &&
             nextContinuation->GetContentOffset() < mContentOffset) {
#ifdef DEBUG
        FrameBidiData nextBidiData = nextContinuation->GetBidiData();
        NS_ASSERTION(bidiData.embeddingLevel == nextBidiData.embeddingLevel &&
                         bidiData.baseLevel == nextBidiData.baseLevel,
                     "stealing text from different type of BIDI continuation");
        MOZ_ASSERT(nextBidiData.precedingControl == kBidiLevelNone,
                   "There shouldn't be any virtual bidi formatting character "
                   "between continuations");
#endif
        nextContinuation->mContentOffset = mContentOffset;
        nextContinuation = nextContinuation->GetNextContinuation();
      }
    }
    AddStateBits(NS_FRAME_IS_BIDI);
  }  // prev frame is bidi
}

void nsContinuingTextFrame::DestroyFrom(nsIFrame* aDestructRoot,
                                        PostDestroyData& aPostDestroyData) {
  ClearFrameOffsetCache();

  // The text associated with this frame will become associated with our
  // prev-continuation. If that means the text has changed style, then
  // we need to wipe out the text run for the text.
  // Note that mPrevContinuation can be null if we're destroying the whole
  // frame chain from the start to the end.
  // If this frame is mentioned in the userData for a textrun (say
  // because there's a direction change at the start of this frame), then
  // we have to clear the textrun because we're going away and the
  // textrun had better not keep a dangling reference to us.
  if (IsInTextRunUserData() ||
      (mPrevContinuation && mPrevContinuation->Style() != Style())) {
    ClearTextRuns();
    // Clear the previous continuation's text run also, so that it can rebuild
    // the text run to include our text.
    if (mPrevContinuation) {
      mPrevContinuation->ClearTextRuns();
    }
  }
  nsSplittableFrame::RemoveFromFlow(this);
  // Let the base class destroy the frame
  nsFrame::DestroyFrom(aDestructRoot, aPostDestroyData);
}

nsIFrame* nsContinuingTextFrame::FirstInFlow() const {
  // Can't cast to |nsContinuingTextFrame*| because the first one isn't.
  nsIFrame *firstInFlow,
      *previous = const_cast<nsIFrame*>(static_cast<const nsIFrame*>(this));
  do {
    firstInFlow = previous;
    previous = firstInFlow->GetPrevInFlow();
  } while (previous);
  MOZ_ASSERT(firstInFlow, "post-condition failed");
  return firstInFlow;
}

nsIFrame* nsContinuingTextFrame::FirstContinuation() const {
  // Can't cast to |nsContinuingTextFrame*| because the first one isn't.
  nsIFrame *firstContinuation,
      *previous = const_cast<nsIFrame*>(
          static_cast<const nsIFrame*>(mPrevContinuation));

  NS_ASSERTION(previous,
               "How can an nsContinuingTextFrame be the first continuation?");

  do {
    firstContinuation = previous;
    previous = firstContinuation->GetPrevContinuation();
  } while (previous);
  MOZ_ASSERT(firstContinuation, "post-condition failed");
  return firstContinuation;
}

// XXX Do we want to do all the work for the first-in-flow or do the
// work for each part?  (Be careful of first-letter / first-line, though,
// especially first-line!)  Doing all the work on the first-in-flow has
// the advantage of avoiding the potential for incremental reflow bugs,
// but depends on our maintining the frame tree in reasonable ways even
// for edge cases (block-within-inline splits, nextBidi, etc.)

// XXX We really need to make :first-letter happen during frame
// construction.

// Needed for text frames in XUL.
/* virtual */ nscoord nsTextFrame::GetMinISize(gfxContext* aRenderingContext) {
  return nsLayoutUtils::MinISizeFromInline(this, aRenderingContext);
}

// Needed for text frames in XUL.
/* virtual */ nscoord nsTextFrame::GetPrefISize(gfxContext* aRenderingContext) {
  return nsLayoutUtils::PrefISizeFromInline(this, aRenderingContext);
}

/* virtual */ void nsContinuingTextFrame::AddInlineMinISize(
    gfxContext* aRenderingContext, InlineMinISizeData* aData) {
  // Do nothing, since the first-in-flow accounts for everything.
}

/* virtual */ void nsContinuingTextFrame::AddInlinePrefISize(
    gfxContext* aRenderingContext, InlinePrefISizeData* aData) {
  // Do nothing, since the first-in-flow accounts for everything.
}

//----------------------------------------------------------------------

#if defined(DEBUG_rbs) || defined(DEBUG_bzbarsky)
static void VerifyNotDirty(nsFrameState state) {
  bool isZero = state & NS_FRAME_FIRST_REFLOW;
  bool isDirty = state & NS_FRAME_IS_DIRTY;
  if (!isZero && isDirty) NS_WARNING("internal offsets may be out-of-sync");
}
#define DEBUG_VERIFY_NOT_DIRTY(state) VerifyNotDirty(state)
#else
#define DEBUG_VERIFY_NOT_DIRTY(state)
#endif

nsIFrame* NS_NewTextFrame(nsIPresShell* aPresShell, ComputedStyle* aStyle) {
  return new (aPresShell) nsTextFrame(aStyle);
}

NS_IMPL_FRAMEARENA_HELPERS(nsTextFrame)

nsIFrame* NS_NewContinuingTextFrame(nsIPresShell* aPresShell,
                                    ComputedStyle* aStyle) {
  return new (aPresShell) nsContinuingTextFrame(aStyle);
}

NS_IMPL_FRAMEARENA_HELPERS(nsContinuingTextFrame)

nsTextFrame::~nsTextFrame() {}

nsresult nsTextFrame::GetCursor(const nsPoint& aPoint,
                                nsIFrame::Cursor& aCursor) {
  FillCursorInformationFromStyle(StyleUI(), aCursor);
  if (NS_STYLE_CURSOR_AUTO == aCursor.mCursor) {
    if (!IsSelectable(nullptr)) {
      aCursor.mCursor = NS_STYLE_CURSOR_DEFAULT;
    } else {
      aCursor.mCursor = GetWritingMode().IsVertical()
                            ? NS_STYLE_CURSOR_VERTICAL_TEXT
                            : NS_STYLE_CURSOR_TEXT;
    }
    return NS_OK;
  } else {
    return nsFrame::GetCursor(aPoint, aCursor);
  }
}

nsTextFrame* nsTextFrame::LastInFlow() const {
  nsTextFrame* lastInFlow = const_cast<nsTextFrame*>(this);
  while (lastInFlow->GetNextInFlow()) {
    lastInFlow = lastInFlow->GetNextInFlow();
  }
  MOZ_ASSERT(lastInFlow, "post-condition failed");
  return lastInFlow;
}

nsTextFrame* nsTextFrame::LastContinuation() const {
  nsTextFrame* lastContinuation = const_cast<nsTextFrame*>(this);
  while (lastContinuation->mNextContinuation) {
    lastContinuation = lastContinuation->mNextContinuation;
  }
  MOZ_ASSERT(lastContinuation, "post-condition failed");
  return lastContinuation;
}

void nsTextFrame::InvalidateFrame(uint32_t aDisplayItemKey,
                                  bool aRebuildDisplayItems) {
  if (nsSVGUtils::IsInSVGTextSubtree(this)) {
    nsIFrame* svgTextFrame = nsLayoutUtils::GetClosestFrameOfType(
        GetParent(), LayoutFrameType::SVGText);
    svgTextFrame->InvalidateFrame();
    return;
  }
  nsFrame::InvalidateFrame(aDisplayItemKey, aRebuildDisplayItems);
}

void nsTextFrame::InvalidateFrameWithRect(const nsRect& aRect,
                                          uint32_t aDisplayItemKey,
                                          bool aRebuildDisplayItems) {
  if (nsSVGUtils::IsInSVGTextSubtree(this)) {
    nsIFrame* svgTextFrame = nsLayoutUtils::GetClosestFrameOfType(
        GetParent(), LayoutFrameType::SVGText);
    svgTextFrame->InvalidateFrame();
    return;
  }
  nsFrame::InvalidateFrameWithRect(aRect, aDisplayItemKey,
                                   aRebuildDisplayItems);
}

gfxTextRun* nsTextFrame::GetUninflatedTextRun() {
  return GetProperty(UninflatedTextRunProperty());
}

void nsTextFrame::SetTextRun(gfxTextRun* aTextRun, TextRunType aWhichTextRun,
                             float aInflation) {
  NS_ASSERTION(aTextRun, "must have text run");

  // Our inflated text run is always stored in mTextRun.  In the cases
  // where our current inflation is not 1.0, however, we store two text
  // runs, and the uninflated one goes in a frame property.  We never
  // store a single text run in both.
  if (aWhichTextRun == eInflated) {
    if (HasFontSizeInflation() && aInflation == 1.0f) {
      // FIXME: Probably shouldn't do this within each SetTextRun
      // method, but it doesn't hurt.
      ClearTextRun(nullptr, nsTextFrame::eNotInflated);
    }
    SetFontSizeInflation(aInflation);
  } else {
    MOZ_ASSERT(aInflation == 1.0f, "unexpected inflation");
    if (HasFontSizeInflation()) {
      // Setting the property will not automatically increment the textrun's
      // reference count, so we need to do it here.
      aTextRun->AddRef();
      SetProperty(UninflatedTextRunProperty(), aTextRun);
      return;
    }
    // fall through to setting mTextRun
  }

  mTextRun = aTextRun;

  // FIXME: Add assertions testing the relationship between
  // GetFontSizeInflation() and whether we have an uninflated text run
  // (but be aware that text runs can go away).
}

bool nsTextFrame::RemoveTextRun(gfxTextRun* aTextRun) {
  if (aTextRun == mTextRun) {
    mTextRun = nullptr;
    mFontMetrics = nullptr;
    return true;
  }
  if ((GetStateBits() & TEXT_HAS_FONT_INFLATION) &&
      GetProperty(UninflatedTextRunProperty()) == aTextRun) {
    DeleteProperty(UninflatedTextRunProperty());
    return true;
  }
  return false;
}

void nsTextFrame::ClearTextRun(nsTextFrame* aStartContinuation,
                               TextRunType aWhichTextRun) {
  RefPtr<gfxTextRun> textRun = GetTextRun(aWhichTextRun);
  if (!textRun) {
    return;
  }

  if (aWhichTextRun == nsTextFrame::eInflated) {
    mFontMetrics = nullptr;
  }

  DebugOnly<bool> checkmTextrun = textRun == mTextRun;
  UnhookTextRunFromFrames(textRun, aStartContinuation);
  MOZ_ASSERT(checkmTextrun ? !mTextRun
                           : !GetProperty(UninflatedTextRunProperty()));
}

void nsTextFrame::DisconnectTextRuns() {
  MOZ_ASSERT(!IsInTextRunUserData(),
             "Textrun mentions this frame in its user data so we can't just "
             "disconnect");
  mTextRun = nullptr;
  if ((GetStateBits() & TEXT_HAS_FONT_INFLATION)) {
    DeleteProperty(UninflatedTextRunProperty());
  }
}

void nsTextFrame::NotifyNativeAnonymousTextnodeChange(uint32_t aOldLength) {
  MOZ_ASSERT(mContent->IsInNativeAnonymousSubtree());

  MarkIntrinsicISizesDirty();

  // This is to avoid making a new Reflow request in CharacterDataChanged:
  for (nsTextFrame* f = this; f; f = f->GetNextContinuation()) {
    f->AddStateBits(NS_FRAME_IS_DIRTY);
    f->mReflowRequestedForCharDataChange = true;
  }

  // Pretend that all the text changed.
  CharacterDataChangeInfo info;
  info.mAppend = false;
  info.mChangeStart = 0;
  info.mChangeEnd = aOldLength;
  info.mReplaceLength = mContent->TextLength();
  CharacterDataChanged(info);
}

nsresult nsTextFrame::CharacterDataChanged(
    const CharacterDataChangeInfo& aInfo) {
  if (mContent->HasFlag(NS_HAS_NEWLINE_PROPERTY)) {
    mContent->DeleteProperty(nsGkAtoms::newline);
    mContent->UnsetFlags(NS_HAS_NEWLINE_PROPERTY);
  }
  if (mContent->HasFlag(NS_HAS_FLOWLENGTH_PROPERTY)) {
    mContent->DeleteProperty(nsGkAtoms::flowlength);
    mContent->UnsetFlags(NS_HAS_FLOWLENGTH_PROPERTY);
  }

  // Find the first frame whose text has changed. Frames that are entirely
  // before the text change are completely unaffected.
  nsTextFrame* next;
  nsTextFrame* textFrame = this;
  while (true) {
    next = textFrame->GetNextContinuation();
    if (!next || next->GetContentOffset() > int32_t(aInfo.mChangeStart)) break;
    textFrame = next;
  }

  int32_t endOfChangedText = aInfo.mChangeStart + aInfo.mReplaceLength;

  // Parent of the last frame that we passed to FrameNeedsReflow (or noticed
  // had already received an earlier FrameNeedsReflow call).
  // (For subsequent frames with this same parent, we can just set their
  // dirty bit without bothering to call FrameNeedsReflow again.)
  nsIFrame* lastDirtiedFrameParent = nullptr;

  nsIPresShell* shell = PresContext()->GetPresShell();
  do {
    // textFrame contained deleted text (or the insertion point,
    // if this was a pure insertion).
    textFrame->RemoveStateBits(TEXT_WHITESPACE_FLAGS);
    textFrame->ClearTextRuns();

    nsIFrame* parentOfTextFrame = textFrame->GetParent();
    bool areAncestorsAwareOfReflowRequest = false;
    if (lastDirtiedFrameParent == parentOfTextFrame) {
      // An earlier iteration of this loop already called
      // FrameNeedsReflow for a sibling of |textFrame|.
      areAncestorsAwareOfReflowRequest = true;
    } else {
      lastDirtiedFrameParent = parentOfTextFrame;
    }

    if (textFrame->mReflowRequestedForCharDataChange) {
      // We already requested a reflow for this frame; nothing to do.
      MOZ_ASSERT(textFrame->HasAnyStateBits(NS_FRAME_IS_DIRTY),
                 "mReflowRequestedForCharDataChange should only be set "
                 "on dirty frames");
    } else {
      // Make sure textFrame is queued up for a reflow.  Also set a flag so we
      // don't waste time doing this again in repeated calls to this method.
      textFrame->mReflowRequestedForCharDataChange = true;
      if (!areAncestorsAwareOfReflowRequest) {
        // Ask the parent frame to reflow me.
        shell->FrameNeedsReflow(textFrame, nsIPresShell::eStyleChange,
                                NS_FRAME_IS_DIRTY);
      } else {
        // We already called FrameNeedsReflow on behalf of an earlier sibling,
        // so we can just mark this frame as dirty and don't need to bother
        // telling its ancestors.
        // Note: if the parent is a block, we're cheating here because we should
        // be marking our line dirty, but we're not. nsTextFrame::SetLength will
        // do that when it gets called during reflow.
        textFrame->AddStateBits(NS_FRAME_IS_DIRTY);
      }
    }
    textFrame->InvalidateFrame();

    // Below, frames that start after the deleted text will be adjusted so that
    // their offsets move with the trailing unchanged text. If this change
    // deletes more text than it inserts, those frame offsets will decrease.
    // We need to maintain the invariant that mContentOffset is non-decreasing
    // along the continuation chain. So we need to ensure that frames that
    // started in the deleted text are all still starting before the
    // unchanged text.
    if (textFrame->mContentOffset > endOfChangedText) {
      textFrame->mContentOffset = endOfChangedText;
    }

    textFrame = textFrame->GetNextContinuation();
  } while (textFrame &&
           textFrame->GetContentOffset() < int32_t(aInfo.mChangeEnd));

  // This is how much the length of the string changed by --- i.e.,
  // how much the trailing unchanged text moved.
  int32_t sizeChange =
      aInfo.mChangeStart + aInfo.mReplaceLength - aInfo.mChangeEnd;

  if (sizeChange) {
    // Fix the offsets of the text frames that start in the trailing
    // unchanged text.
    while (textFrame) {
      textFrame->mContentOffset += sizeChange;
      // XXX we could rescue some text runs by adjusting their user data
      // to reflect the change in DOM offsets
      textFrame->ClearTextRuns();
      textFrame = textFrame->GetNextContinuation();
    }
  }

  return NS_OK;
}

class nsDisplayText final : public nsCharClipDisplayItem {
 public:
  nsDisplayText(nsDisplayListBuilder* aBuilder, nsTextFrame* aFrame,
                const Maybe<bool>& aIsSelected);
#ifdef NS_BUILD_REFCNT_LOGGING
  virtual ~nsDisplayText() { MOZ_COUNT_DTOR(nsDisplayText); }
#endif

  void RestoreState() final {
    nsCharClipDisplayItem::RestoreState();
    mOpacity = 1.0f;
  }

  nsRect GetBounds(nsDisplayListBuilder* aBuilder, bool* aSnap) const final {
    *aSnap = false;
    return mBounds;
  }
  void HitTest(nsDisplayListBuilder* aBuilder, const nsRect& aRect,
               HitTestState* aState, nsTArray<nsIFrame*>* aOutFrames) final {
    if (nsRect(ToReferenceFrame(), mFrame->GetSize()).Intersects(aRect)) {
      aOutFrames->AppendElement(mFrame);
    }
  }
  bool CreateWebRenderCommands(mozilla::wr::DisplayListBuilder& aBuilder,
                               mozilla::wr::IpcResourceUpdateQueue& aResources,
                               const StackingContextHelper& aSc,
                               RenderRootStateManager* aManager,
                               nsDisplayListBuilder* aDisplayListBuilder) final;
  void Paint(nsDisplayListBuilder* aBuilder, gfxContext* aCtx) final;
  NS_DISPLAY_DECL_NAME("Text", TYPE_TEXT)

  nsRect GetComponentAlphaBounds(nsDisplayListBuilder* aBuilder) const final {
    if (gfxPlatform::GetPlatform()->RespectsFontStyleSmoothing()) {
      // On OS X, web authors can turn off subpixel text rendering using the
      // CSS property -moz-osx-font-smoothing. If they do that, we don't need
      // to use component alpha layers for the affected text.
      if (mFrame->StyleFont()->mFont.smoothing == NS_FONT_SMOOTHING_GRAYSCALE) {
        return nsRect();
      }
    }
    bool snap;
    return GetBounds(aBuilder, &snap);
  }

  nsDisplayItemGeometry* AllocateGeometry(nsDisplayListBuilder* aBuilder) final;

  void ComputeInvalidationRegion(nsDisplayListBuilder* aBuilder,
                                 const nsDisplayItemGeometry* aGeometry,
                                 nsRegion* aInvalidRegion) const final;

  void RenderToContext(gfxContext* aCtx, nsDisplayListBuilder* aBuilder,
                       bool aIsRecording = false);

  bool CanApplyOpacity() const final {
    if (IsSelected()) {
      return false;
    }

    nsTextFrame* f = static_cast<nsTextFrame*>(mFrame);
    const nsStyleText* textStyle = f->StyleText();
    if (textStyle->mTextShadow) {
      return false;
    }

    nsTextFrame::TextDecorations decorations;
    f->GetTextDecorations(f->PresContext(), nsTextFrame::eResolvedColors,
                          decorations);
    if (decorations.HasDecorationLines()) {
      return false;
    }

    return true;
  }

  void ApplyOpacity(nsDisplayListBuilder* aBuilder, float aOpacity,
                    const DisplayItemClipChain* aClip) final {
    NS_ASSERTION(CanApplyOpacity(), "ApplyOpacity should be allowed");
    mOpacity = aOpacity;
    IntersectClip(aBuilder, aClip, false);
  }

  void WriteDebugInfo(std::stringstream& aStream) final {
#ifdef DEBUG
    aStream << " (\"";

    nsTextFrame* f = static_cast<nsTextFrame*>(mFrame);
    nsCString buf;
    int32_t totalContentLength;
    f->ToCString(buf, &totalContentLength);

    aStream << buf.get() << "\")";
#endif
  }

  nsRect mBounds;
  float mOpacity;
};

class nsDisplayTextGeometry : public nsCharClipGeometry {
 public:
  nsDisplayTextGeometry(nsDisplayText* aItem, nsDisplayListBuilder* aBuilder)
      : nsCharClipGeometry(aItem, aBuilder), mOpacity(aItem->mOpacity) {
    nsTextFrame* f = static_cast<nsTextFrame*>(aItem->Frame());
    f->GetTextDecorations(f->PresContext(), nsTextFrame::eResolvedColors,
                          mDecorations);
  }

  /**
   * We store the computed text decorations here since they are
   * computed using style data from parent frames. Any changes to these
   * styles will only invalidate the parent frame and not this frame.
   */
  nsTextFrame::TextDecorations mDecorations;
  float mOpacity;
};

nsDisplayItemGeometry* nsDisplayText::AllocateGeometry(
    nsDisplayListBuilder* aBuilder) {
  return new nsDisplayTextGeometry(this, aBuilder);
}

void nsDisplayText::ComputeInvalidationRegion(
    nsDisplayListBuilder* aBuilder, const nsDisplayItemGeometry* aGeometry,
    nsRegion* aInvalidRegion) const {
  const nsDisplayTextGeometry* geometry =
      static_cast<const nsDisplayTextGeometry*>(aGeometry);
  nsTextFrame* f = static_cast<nsTextFrame*>(mFrame);

  nsTextFrame::TextDecorations decorations;
  f->GetTextDecorations(f->PresContext(), nsTextFrame::eResolvedColors,
                        decorations);

  bool snap;
  nsRect newRect = geometry->mBounds;
  nsRect oldRect = GetBounds(aBuilder, &snap);
  if (decorations != geometry->mDecorations ||
      mVisIStartEdge != geometry->mVisIStartEdge ||
      mVisIEndEdge != geometry->mVisIEndEdge ||
      !oldRect.IsEqualInterior(newRect) ||
      !geometry->mBorderRect.IsEqualInterior(GetBorderRect()) ||
      mOpacity != geometry->mOpacity) {
    aInvalidRegion->Or(oldRect, newRect);
  }
}

NS_DECLARE_FRAME_PROPERTY_SMALL_VALUE(TextCombineScaleFactorProperty, float)

static float GetTextCombineScaleFactor(nsTextFrame* aFrame) {
  float factor = aFrame->GetProperty(TextCombineScaleFactorProperty());
  return factor ? factor : 1.0f;
}

nsDisplayText::nsDisplayText(nsDisplayListBuilder* aBuilder,
                             nsTextFrame* aFrame,
                             const Maybe<bool>& aIsSelected)
    : nsCharClipDisplayItem(aBuilder, aFrame), mOpacity(1.0f) {
  MOZ_COUNT_CTOR(nsDisplayText);
  mIsFrameSelected = aIsSelected;
  mBounds = mFrame->GetVisualOverflowRectRelativeToSelf() + ToReferenceFrame();
  // Bug 748228
  mBounds.Inflate(mFrame->PresContext()->AppUnitsPerDevPixel());
}

void nsDisplayText::Paint(nsDisplayListBuilder* aBuilder, gfxContext* aCtx) {
  AUTO_PROFILER_LABEL("nsDisplayText::Paint", GRAPHICS);

  DrawTargetAutoDisableSubpixelAntialiasing disable(aCtx->GetDrawTarget(),
                                                    mDisableSubpixelAA);
  RenderToContext(aCtx, aBuilder);
}

bool nsDisplayText::CreateWebRenderCommands(
    mozilla::wr::DisplayListBuilder& aBuilder,
    mozilla::wr::IpcResourceUpdateQueue& aResources,
    const StackingContextHelper& aSc, RenderRootStateManager* aManager,
    nsDisplayListBuilder* aDisplayListBuilder) {
  if (mBounds.IsEmpty()) {
    return true;
  }

  auto appUnitsPerDevPixel = Frame()->PresContext()->AppUnitsPerDevPixel();
  gfx::Point deviceOffset =
      LayoutDevicePoint::FromAppUnits(mBounds.TopLeft(), appUnitsPerDevPixel)
          .ToUnknownPoint();

  nsRect visible = GetPaintRect();
  visible.Inflate(3 * appUnitsPerDevPixel);

  visible = visible.Intersect(mBounds);

  RefPtr<gfxContext> textDrawer = aBuilder.GetTextContext(
      aResources, aSc, aManager, this, visible, deviceOffset);

  RenderToContext(textDrawer, aDisplayListBuilder, true);

  return textDrawer->GetTextDrawer()->Finish();
}

void nsDisplayText::RenderToContext(gfxContext* aCtx,
                                    nsDisplayListBuilder* aBuilder,
                                    bool aIsRecording) {
  nsTextFrame* f = static_cast<nsTextFrame*>(mFrame);

  // Add 1 pixel of dirty area around mVisibleRect to allow us to paint
  // antialiased pixels beyond the measured text extents.
  // This is temporary until we do this in the actual calculation of text
  // extents.
  auto A2D = mFrame->PresContext()->AppUnitsPerDevPixel();
  LayoutDeviceRect extraVisible =
      LayoutDeviceRect::FromAppUnits(GetPaintRect(), A2D);
  extraVisible.Inflate(1);

  gfxRect pixelVisible(extraVisible.x, extraVisible.y, extraVisible.width,
                       extraVisible.height);
  pixelVisible.Inflate(2);
  pixelVisible.RoundOut();

  bool willClip = !aBuilder->IsForGenerateGlyphMask() &&
                  !aBuilder->IsForPaintingSelectionBG() && !aIsRecording;
  if (willClip) {
    aCtx->NewPath();
    aCtx->Rectangle(pixelVisible);
    aCtx->Clip();
  }

  NS_ASSERTION(mVisIStartEdge >= 0, "illegal start edge");
  NS_ASSERTION(mVisIEndEdge >= 0, "illegal end edge");

  gfxContextMatrixAutoSaveRestore matrixSR;

  nsPoint framePt = ToReferenceFrame();
  if (f->Style()->IsTextCombined()) {
    float scaleFactor = GetTextCombineScaleFactor(f);
    if (scaleFactor != 1.0f) {
      if (auto* textDrawer = aCtx->GetTextDrawer()) {
        // WebRender doesn't support scaling text like this yet
        textDrawer->FoundUnsupportedFeature();
        return;
      }
      matrixSR.SetContext(aCtx);
      // Setup matrix to compress text for text-combine-upright if
      // necessary. This is done here because we want selection be
      // compressed at the same time as text.
      gfxPoint pt = nsLayoutUtils::PointToGfxPoint(framePt, A2D);
      gfxMatrix mat = aCtx->CurrentMatrixDouble()
                          .PreTranslate(pt)
                          .PreScale(scaleFactor, 1.0)
                          .PreTranslate(-pt);
      aCtx->SetMatrixDouble(mat);
    }
  }
  nsTextFrame::PaintTextParams params(aCtx);
  params.framePt = gfx::Point(framePt.x, framePt.y);
  params.dirtyRect = extraVisible;

  if (aBuilder->IsForGenerateGlyphMask()) {
    MOZ_ASSERT(!aBuilder->IsForPaintingSelectionBG());
    params.state = nsTextFrame::PaintTextParams::GenerateTextMask;
  } else if (aBuilder->IsForPaintingSelectionBG()) {
    params.state = nsTextFrame::PaintTextParams::PaintTextBGColor;
  } else {
    params.state = nsTextFrame::PaintTextParams::PaintText;
  }

  f->PaintText(params, *this, mOpacity);

  if (willClip) {
    aCtx->PopClip();
  }
}

void nsTextFrame::BuildDisplayList(nsDisplayListBuilder* aBuilder,
                                   const nsDisplayListSet& aLists) {
  if (!IsVisibleForPainting()) return;

  DO_GLOBAL_REFLOW_COUNT_DSP("nsTextFrame");

  const nsStyleText* st = StyleText();
  bool isTextTransparent =
      NS_GET_A(st->mWebkitTextFillColor.CalcColor(this)) == 0 &&
      NS_GET_A(st->mWebkitTextStrokeColor.CalcColor(this)) == 0;
  Maybe<bool> isSelected;
  if (((GetStateBits() & TEXT_NO_RENDERED_GLYPHS) ||
       (isTextTransparent && !StyleText()->HasTextShadow())) &&
      aBuilder->IsForPainting() && !nsSVGUtils::IsInSVGTextSubtree(this)) {
    isSelected.emplace(IsSelected());
    if (!isSelected.value()) {
      TextDecorations textDecs;
      GetTextDecorations(PresContext(), eResolvedColors, textDecs);
      if (!textDecs.HasDecorationLines()) {
        return;
      }
    }
  }

  aLists.Content()->AppendToTop(
      MakeDisplayItem<nsDisplayText>(aBuilder, this, isSelected));
}

static nsIFrame* GetGeneratedContentOwner(nsIFrame* aFrame, bool* aIsBefore) {
  *aIsBefore = false;
  while (aFrame && (aFrame->GetStateBits() & NS_FRAME_GENERATED_CONTENT)) {
    if (aFrame->Style()->GetPseudo() == nsCSSPseudoElements::before()) {
      *aIsBefore = true;
    }
    aFrame = aFrame->GetParent();
  }
  return aFrame;
}

UniquePtr<SelectionDetails> nsTextFrame::GetSelectionDetails() {
  const nsFrameSelection* frameSelection = GetConstFrameSelection();
  if (frameSelection->GetTableCellSelection()) {
    return nullptr;
  }
  if (!(GetStateBits() & NS_FRAME_GENERATED_CONTENT)) {
    UniquePtr<SelectionDetails> details = frameSelection->LookUpSelection(
        mContent, GetContentOffset(), GetContentLength(), false);
    for (SelectionDetails* sd = details.get(); sd; sd = sd->mNext.get()) {
      sd->mStart += mContentOffset;
      sd->mEnd += mContentOffset;
    }
    return details;
  }

  // Check if the beginning or end of the element is selected, depending on
  // whether we're :before content or :after content.
  bool isBefore;
  nsIFrame* owner = GetGeneratedContentOwner(this, &isBefore);
  if (!owner || !owner->GetContent()) return nullptr;

  UniquePtr<SelectionDetails> details = frameSelection->LookUpSelection(
      owner->GetContent(), isBefore ? 0 : owner->GetContent()->GetChildCount(),
      0, false);
  for (SelectionDetails* sd = details.get(); sd; sd = sd->mNext.get()) {
    // The entire text is selected!
    sd->mStart = GetContentOffset();
    sd->mEnd = GetContentEnd();
  }
  return details;
}

static void PaintSelectionBackground(
    DrawTarget& aDrawTarget, nscolor aColor, const LayoutDeviceRect& aDirtyRect,
    const LayoutDeviceRect& aRect, nsTextFrame::DrawPathCallbacks* aCallbacks) {
  Rect rect = aRect.Intersect(aDirtyRect).ToUnknownRect();
  MaybeSnapToDevicePixels(rect, aDrawTarget);

  if (aCallbacks) {
    aCallbacks->NotifySelectionBackgroundNeedsFill(rect, aColor, aDrawTarget);
  } else {
    ColorPattern color(ToDeviceColor(aColor));
    aDrawTarget.FillRect(rect, color);
  }
}

// Attempt to get the LineBaselineOffset property of aChildFrame
// If not set, calculate this value for all child frames of aBlockFrame
static nscoord LazyGetLineBaselineOffset(nsIFrame* aChildFrame,
                                         nsBlockFrame* aBlockFrame) {
  bool offsetFound;
  nscoord offset =
      aChildFrame->GetProperty(nsIFrame::LineBaselineOffset(), &offsetFound);

  if (!offsetFound) {
    for (nsBlockFrame::LineIterator line = aBlockFrame->LinesBegin(),
                                    line_end = aBlockFrame->LinesEnd();
         line != line_end; line++) {
      if (line->IsInline()) {
        int32_t n = line->GetChildCount();
        nscoord lineBaseline = line->BStart() + line->GetLogicalAscent();
        for (nsIFrame* lineFrame = line->mFirstChild; n > 0;
             lineFrame = lineFrame->GetNextSibling(), --n) {
          offset = lineBaseline - lineFrame->GetNormalPosition().y;
          lineFrame->SetProperty(nsIFrame::LineBaselineOffset(), offset);
        }
      }
    }
    return aChildFrame->GetProperty(nsIFrame::LineBaselineOffset(),
                                    &offsetFound);
  } else {
    return offset;
  }
}

static bool IsUnderlineRight(nsIFrame* aFrame) {
  nsAtom* langAtom = aFrame->StyleFont()->mLanguage;
  if (!langAtom) {
    return false;
  }
  nsAtomString langStr(langAtom);
  return (StringBeginsWith(langStr, NS_LITERAL_STRING("ja")) ||
          StringBeginsWith(langStr, NS_LITERAL_STRING("ko"))) &&
         (langStr.Length() == 2 || langStr[2] == '-');
}

void nsTextFrame::GetTextDecorations(
    nsPresContext* aPresContext,
    nsTextFrame::TextDecorationColorResolution aColorResolution,
    nsTextFrame::TextDecorations& aDecorations) {
  const nsCompatibility compatMode = aPresContext->CompatibilityMode();

  bool useOverride = false;
  nscolor overrideColor = NS_RGBA(0, 0, 0, 0);

  bool nearestBlockFound = false;
  // Use writing mode of parent frame for orthogonal text frame to work.
  // See comment in nsTextFrame::DrawTextRunAndDecorations.
  WritingMode wm = GetParent()->GetWritingMode();
  bool vertical = wm.IsVertical();

  nscoord ascent = GetLogicalBaseline(wm);
  // physicalBlockStartOffset represents the offset from our baseline
  // to f's physical block start, which is top in horizontal writing
  // mode, and left in vertical writing modes, in our coordinate space.
  // This physical block start is logical block start in most cases,
  // but for vertical-rl, it is logical block end, and consequently in
  // that case, it starts from the descent instead of ascent.
  nscoord physicalBlockStartOffset =
      wm.IsVerticalRL() ? GetSize().width - ascent : ascent;
  // baselineOffset represents the offset from our baseline to f's baseline or
  // the nearest block's baseline, in our coordinate space, whichever is closest
  // during the particular iteration
  nscoord baselineOffset = 0;

  for (nsIFrame *f = this, *fChild = nullptr; f;
       fChild = f, f = nsLayoutUtils::GetParentOrPlaceholderFor(f)) {
    ComputedStyle* const context = f->Style();
    if (!context->HasTextDecorationLines()) {
      break;
    }

    const nsStyleTextReset* const styleText = context->StyleTextReset();
    const uint8_t textDecorations = styleText->mTextDecorationLine;

    if (!useOverride &&
        (NS_STYLE_TEXT_DECORATION_LINE_OVERRIDE_ALL & textDecorations)) {
      // This handles the <a href="blah.html"><font color="green">La
      // la la</font></a> case. The link underline should be green.
      useOverride = true;
      overrideColor =
          nsLayoutUtils::GetColor(f, &nsStyleTextReset::mTextDecorationColor);
    }

    nsBlockFrame* fBlock = nsLayoutUtils::GetAsBlock(f);
    const bool firstBlock = !nearestBlockFound && fBlock;

    // Not updating positions once we hit a parent block is equivalent to
    // the CSS 2.1 spec that blocks should propagate decorations down to their
    // children (albeit the style should be preserved)
    // However, if we're vertically aligned within a block, then we need to
    // recover the correct baseline from the line by querying the FrameProperty
    // that should be set (see nsLineLayout::VerticalAlignLine).
    if (firstBlock) {
      // At this point, fChild can't be null since TextFrames can't be blocks
      if (fChild->VerticalAlignEnum() != NS_STYLE_VERTICAL_ALIGN_BASELINE) {
        // Since offset is the offset in the child's coordinate space, we have
        // to undo the accumulation to bring the transform out of the block's
        // coordinate space
        const nscoord lineBaselineOffset =
            LazyGetLineBaselineOffset(fChild, fBlock);

        baselineOffset = physicalBlockStartOffset - lineBaselineOffset -
                         (vertical ? fChild->GetNormalPosition().x
                                   : fChild->GetNormalPosition().y);
      }
    } else if (!nearestBlockFound) {
      // offset here is the offset from f's baseline to f's top/left
      // boundary. It's descent for vertical-rl, and ascent otherwise.
      nscoord offset = wm.IsVerticalRL()
                           ? f->GetSize().width - f->GetLogicalBaseline(wm)
                           : f->GetLogicalBaseline(wm);
      baselineOffset = physicalBlockStartOffset - offset;
    }

    nearestBlockFound = nearestBlockFound || firstBlock;
    physicalBlockStartOffset +=
        vertical ? f->GetNormalPosition().x : f->GetNormalPosition().y;

    const uint8_t style = styleText->mTextDecorationStyle;
    if (textDecorations) {
      nscolor color;
      if (useOverride) {
        color = overrideColor;
      } else if (nsSVGUtils::IsInSVGTextSubtree(this)) {
        // XXX We might want to do something with text-decoration-color when
        //     painting SVG text, but it's not clear what we should do.  We
        //     at least need SVG text decorations to paint with 'fill' if
        //     text-decoration-color has its initial value currentColor.
        //     We could choose to interpret currentColor as "currentFill"
        //     for SVG text, and have e.g. text-decoration-color:red to
        //     override the fill paint of the decoration.
        color = aColorResolution == eResolvedColors
                    ? nsLayoutUtils::GetColor(f, &nsStyleSVG::mFill)
                    : NS_SAME_AS_FOREGROUND_COLOR;
      } else {
        color =
            nsLayoutUtils::GetColor(f, &nsStyleTextReset::mTextDecorationColor);
      }

      bool swapUnderlineAndOverline = vertical && IsUnderlineRight(f);
      const uint8_t kUnderline = swapUnderlineAndOverline
                                     ? NS_STYLE_TEXT_DECORATION_LINE_OVERLINE
                                     : NS_STYLE_TEXT_DECORATION_LINE_UNDERLINE;
      const uint8_t kOverline = swapUnderlineAndOverline
                                    ? NS_STYLE_TEXT_DECORATION_LINE_UNDERLINE
                                    : NS_STYLE_TEXT_DECORATION_LINE_OVERLINE;

      if (textDecorations & kUnderline) {
        aDecorations.mUnderlines.AppendElement(
            nsTextFrame::LineDecoration(f, baselineOffset, color, style));
      }
      if (textDecorations & kOverline) {
        aDecorations.mOverlines.AppendElement(
            nsTextFrame::LineDecoration(f, baselineOffset, color, style));
      }
      if (textDecorations & NS_STYLE_TEXT_DECORATION_LINE_LINE_THROUGH) {
        aDecorations.mStrikes.AppendElement(
            nsTextFrame::LineDecoration(f, baselineOffset, color, style));
      }
    }

    // In all modes, if we're on an inline-block or inline-table (or
    // inline-stack, inline-box, inline-grid), we're done.
    // If we're on a ruby frame other than ruby text container, we
    // should continue.
    mozilla::StyleDisplay display = f->GetDisplay();
    if (display != mozilla::StyleDisplay::Inline &&
        (!nsStyleDisplay::IsRubyDisplayType(display) ||
         display == mozilla::StyleDisplay::RubyTextContainer) &&
        nsStyleDisplay::IsDisplayTypeInlineOutside(display)) {
      break;
    }

    // In quirks mode, if we're on an HTML table element, we're done.
    if (compatMode == eCompatibility_NavQuirks &&
        f->GetContent()->IsHTMLElement(nsGkAtoms::table)) {
      break;
    }

    // If we're on an absolutely-positioned element or a floating
    // element, we're done.
    if (f->IsFloating() || f->IsAbsolutelyPositioned()) {
      break;
    }

    // If we're an outer <svg> element, which is classified as an atomic
    // inline-level element, we're done.
    if (f->IsSVGOuterSVGFrame()) {
      break;
    }
  }
}

static float GetInflationForTextDecorations(nsIFrame* aFrame,
                                            nscoord aInflationMinFontSize) {
  if (nsSVGUtils::IsInSVGTextSubtree(aFrame)) {
    const nsIFrame* container = aFrame;
    while (!container->IsSVGTextFrame()) {
      container = container->GetParent();
    }
    NS_ASSERTION(container, "expected to find an ancestor SVGTextFrame");
    return static_cast<const SVGTextFrame*>(container)
        ->GetFontSizeScaleFactor();
  }
  return nsLayoutUtils::FontSizeInflationInner(aFrame, aInflationMinFontSize);
}

struct EmphasisMarkInfo {
  RefPtr<gfxTextRun> textRun;
  gfxFloat advance;
  gfxFloat baselineOffset;
};

NS_DECLARE_FRAME_PROPERTY_DELETABLE(EmphasisMarkProperty, EmphasisMarkInfo)

static already_AddRefed<gfxTextRun> GenerateTextRunForEmphasisMarks(
    nsTextFrame* aFrame, gfxFontGroup* aFontGroup,
    ComputedStyle* aComputedStyle, const nsStyleText* aStyleText) {
  const nsString& emphasisString = aStyleText->mTextEmphasisStyleString;
  RefPtr<DrawTarget> dt = CreateReferenceDrawTarget(aFrame);
  auto appUnitsPerDevUnit = aFrame->PresContext()->AppUnitsPerDevPixel();
  gfx::ShapedTextFlags flags =
      nsLayoutUtils::GetTextRunOrientFlagsForStyle(aComputedStyle);
  if (flags == gfx::ShapedTextFlags::TEXT_ORIENT_VERTICAL_MIXED) {
    // The emphasis marks should always be rendered upright per spec.
    flags = gfx::ShapedTextFlags::TEXT_ORIENT_VERTICAL_UPRIGHT;
  }
  return aFontGroup->MakeTextRun<char16_t>(
      emphasisString.get(), emphasisString.Length(), dt, appUnitsPerDevUnit,
      flags, nsTextFrameUtils::Flags(), nullptr);
}

static nsRubyFrame* FindFurthestInlineRubyAncestor(nsTextFrame* aFrame) {
  nsRubyFrame* rubyFrame = nullptr;
  for (nsIFrame* frame = aFrame->GetParent();
       frame && frame->IsFrameOfType(nsIFrame::eLineParticipant);
       frame = frame->GetParent()) {
    if (frame->IsRubyFrame()) {
      rubyFrame = static_cast<nsRubyFrame*>(frame);
    }
  }
  return rubyFrame;
}

nsRect nsTextFrame::UpdateTextEmphasis(WritingMode aWM,
                                       PropertyProvider& aProvider) {
  const nsStyleText* styleText = StyleText();
  if (!styleText->HasTextEmphasis()) {
    DeleteProperty(EmphasisMarkProperty());
    return nsRect();
  }

  ComputedStyle* computedStyle = Style();
  bool isTextCombined = computedStyle->IsTextCombined();
  if (isTextCombined) {
    computedStyle = GetParent()->Style();
  }
  RefPtr<nsFontMetrics> fm = nsLayoutUtils::GetFontMetricsOfEmphasisMarks(
      computedStyle, PresContext(), GetFontSizeInflation());
  EmphasisMarkInfo* info = new EmphasisMarkInfo;
  info->textRun = GenerateTextRunForEmphasisMarks(
      this, fm->GetThebesFontGroup(), computedStyle, styleText);
  info->advance = info->textRun->GetAdvanceWidth();

  // Calculate the baseline offset
  LogicalSide side = styleText->TextEmphasisSide(aWM);
  LogicalSize frameSize = GetLogicalSize(aWM);
  // The overflow rect is inflated in the inline direction by half
  // advance of the emphasis mark on each side, so that even if a mark
  // is drawn for a zero-width character, it won't be clipped.
  LogicalRect overflowRect(aWM, -info->advance / 2,
                           /* BStart to be computed below */ 0,
                           frameSize.ISize(aWM) + info->advance,
                           fm->MaxAscent() + fm->MaxDescent());
  RefPtr<nsFontMetrics> baseFontMetrics =
      isTextCombined
          ? nsLayoutUtils::GetInflatedFontMetricsForFrame(GetParent())
          : do_AddRef(aProvider.GetFontMetrics());
  // When the writing mode is vertical-lr the line is inverted, and thus
  // the ascent and descent are swapped.
  nscoord absOffset = (side == eLogicalSideBStart) != aWM.IsLineInverted()
                          ? baseFontMetrics->MaxAscent() + fm->MaxDescent()
                          : baseFontMetrics->MaxDescent() + fm->MaxAscent();
  RubyBlockLeadings leadings;
  if (nsRubyFrame* ruby = FindFurthestInlineRubyAncestor(this)) {
    leadings = ruby->GetBlockLeadings();
  }
  if (side == eLogicalSideBStart) {
    info->baselineOffset = -absOffset - leadings.mStart;
    overflowRect.BStart(aWM) = -overflowRect.BSize(aWM) - leadings.mStart;
  } else {
    MOZ_ASSERT(side == eLogicalSideBEnd);
    info->baselineOffset = absOffset + leadings.mEnd;
    overflowRect.BStart(aWM) = frameSize.BSize(aWM) + leadings.mEnd;
  }
  // If text combined, fix the gap between the text frame and its parent.
  if (isTextCombined) {
    nscoord gap = (baseFontMetrics->MaxHeight() - frameSize.BSize(aWM)) / 2;
    overflowRect.BStart(aWM) += gap * (side == eLogicalSideBStart ? -1 : 1);
  }

  SetProperty(EmphasisMarkProperty(), info);
  return overflowRect.GetPhysicalRect(aWM, frameSize.GetPhysicalSize(aWM));
}

void nsTextFrame::UnionAdditionalOverflow(nsPresContext* aPresContext,
                                          nsIFrame* aBlock,
                                          PropertyProvider& aProvider,
                                          nsRect* aVisualOverflowRect,
                                          bool aIncludeTextDecorations) {
  const WritingMode wm = GetWritingMode();
  bool verticalRun = mTextRun->IsVertical();
  const gfxFloat appUnitsPerDevUnit = aPresContext->AppUnitsPerDevPixel();

  if (IsFloatingFirstLetterChild()) {
    bool inverted = wm.IsLineInverted();
    // The underline/overline drawable area must be contained in the overflow
    // rect when this is in floating first letter frame at *both* modes.
    // In this case, aBlock is the ::first-letter frame.
    uint8_t decorationStyle =
        aBlock->Style()->StyleTextReset()->mTextDecorationStyle;
    // If the style is none, let's include decoration line rect as solid style
    // since changing the style from none to solid/dotted/dashed doesn't cause
    // reflow.
    if (decorationStyle == NS_STYLE_TEXT_DECORATION_STYLE_NONE) {
      decorationStyle = NS_STYLE_TEXT_DECORATION_STYLE_SOLID;
    }
    nsFontMetrics* fontMetrics = aProvider.GetFontMetrics();
    nscoord underlineOffset, underlineSize;
    fontMetrics->GetUnderline(underlineOffset, underlineSize);
    nscoord maxAscent =
        inverted ? fontMetrics->MaxDescent() : fontMetrics->MaxAscent();

    nsCSSRendering::DecorationRectParams params;
    Float gfxWidth = (verticalRun ? aVisualOverflowRect->height
                                  : aVisualOverflowRect->width) /
                     appUnitsPerDevUnit;
    params.lineSize = Size(gfxWidth, underline