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

#include "CounterStyleManager.h"

#include <type_traits>

#include "mozilla/ArenaObjectID.h"
#include "mozilla/ArrayUtils.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/PresShell.h"
#include "mozilla/Types.h"
#include "mozilla/WritingModes.h"
#include "nsPresContext.h"
#include "nsPresContextInlines.h"
#include "nsString.h"
#include "nsTArray.h"
#include "nsTHashtable.h"
#include "nsUnicodeProperties.h"
#include "mozilla/ServoBindings.h"
#include "mozilla/ServoStyleSet.h"

namespace mozilla {

using AdditiveSymbol = StyleAdditiveSymbol;

struct NegativeType {
  nsString before, after;
};

struct PadType {
  int32_t width;
  nsString symbol;
};

// This limitation will be applied to some systems, and pad descriptor.
// Any initial representation generated by symbolic or additive which is
// longer than this limitation will be dropped. If any pad is longer
// than this, the whole counter text will be dropped as well.
// The spec requires user agents to support at least 60 Unicode code-
// points for counter text. However, this constant only limits the
// length in 16-bit units. So it has to be at least 120, since code-
// points outside the BMP will need 2 16-bit units.
#define LENGTH_LIMIT 150

static bool GetCyclicCounterText(CounterValue aOrdinal, nsAString& aResult,
                                 Span<const nsString> aSymbols) {
  MOZ_ASSERT(aSymbols.Length() >= 1, "No symbol available for cyclic counter.");
  auto n = aSymbols.Length();
  CounterValue index = (aOrdinal - 1) % n;
  aResult = aSymbols[index >= 0 ? index : index + n];
  return true;
}

static bool GetFixedCounterText(CounterValue aOrdinal, nsAString& aResult,
                                CounterValue aStart,
                                Span<const nsString> aSymbols) {
  CounterValue index = aOrdinal - aStart;
  if (index >= 0 && index < CounterValue(aSymbols.Length())) {
    aResult = aSymbols[index];
    return true;
  } else {
    return false;
  }
}

static bool GetSymbolicCounterText(CounterValue aOrdinal, nsAString& aResult,
                                   Span<const nsString> aSymbols) {
  MOZ_ASSERT(aSymbols.Length() >= 1,
             "No symbol available for symbolic counter.");
  MOZ_ASSERT(aOrdinal >= 0, "Invalid ordinal.");
  if (aOrdinal == 0) {
    return false;
  }

  aResult.Truncate();
  auto n = aSymbols.Length();
  const nsString& symbol = aSymbols[(aOrdinal - 1) % n];
  size_t len = (aOrdinal + n - 1) / n;
  auto symbolLength = symbol.Length();
  if (symbolLength > 0) {
    if (len > LENGTH_LIMIT || symbolLength > LENGTH_LIMIT ||
        len * symbolLength > LENGTH_LIMIT) {
      return false;
    }
    for (size_t i = 0; i < len; ++i) {
      aResult.Append(symbol);
    }
  }
  return true;
}

static bool GetAlphabeticCounterText(CounterValue aOrdinal, nsAString& aResult,
                                     Span<const nsString> aSymbols) {
  MOZ_ASSERT(aSymbols.Length() >= 2, "Too few symbols for alphabetic counter.");
  MOZ_ASSERT(aOrdinal >= 0, "Invalid ordinal.");
  if (aOrdinal == 0) {
    return false;
  }

  auto n = aSymbols.Length();
  // The precise length of this array should be
  // ceil(log((double) aOrdinal / n * (n - 1) + 1) / log(n)).
  // The max length is slightly smaller than which defined below.
  AutoTArray<int32_t, std::numeric_limits<CounterValue>::digits> indexes;
  while (aOrdinal > 0) {
    --aOrdinal;
    indexes.AppendElement(aOrdinal % n);
    aOrdinal /= n;
  }

  aResult.Truncate();
  for (auto i = indexes.Length(); i > 0; --i) {
    aResult.Append(aSymbols[indexes[i - 1]]);
  }
  return true;
}

static bool GetNumericCounterText(CounterValue aOrdinal, nsAString& aResult,
                                  Span<const nsString> aSymbols) {
  MOZ_ASSERT(aSymbols.Length() >= 2, "Too few symbols for numeric counter.");
  MOZ_ASSERT(aOrdinal >= 0, "Invalid ordinal.");

  if (aOrdinal == 0) {
    aResult = aSymbols[0];
    return true;
  }

  auto n = aSymbols.Length();
  AutoTArray<int32_t, std::numeric_limits<CounterValue>::digits> indexes;
  while (aOrdinal > 0) {
    indexes.AppendElement(aOrdinal % n);
    aOrdinal /= n;
  }

  aResult.Truncate();
  for (auto i = indexes.Length(); i > 0; --i) {
    aResult.Append(aSymbols[indexes[i - 1]]);
  }
  return true;
}

static bool GetAdditiveCounterText(CounterValue aOrdinal, nsAString& aResult,
                                   Span<const AdditiveSymbol> aSymbols) {
  MOZ_ASSERT(aOrdinal >= 0, "Invalid ordinal.");

  if (aOrdinal == 0) {
    const AdditiveSymbol& last = aSymbols[aSymbols.Length() - 1];
    if (last.weight == 0) {
      aResult = last.symbol;
      return true;
    }
    return false;
  }

  aResult.Truncate();
  size_t length = 0;
  for (size_t i = 0, iEnd = aSymbols.Length(); i < iEnd; ++i) {
    const AdditiveSymbol& symbol = aSymbols[i];
    if (symbol.weight == 0) {
      break;
    }
    CounterValue times = aOrdinal / symbol.weight;
    if (times > 0) {
      auto symbolLength = symbol.symbol.Length();
      if (symbolLength > 0) {
        length += times * symbolLength;
        if (times > LENGTH_LIMIT || symbolLength > LENGTH_LIMIT ||
            length > LENGTH_LIMIT) {
          return false;
        }
        for (CounterValue j = 0; j < times; ++j) {
          aResult.Append(symbol.symbol);
        }
      }
      aOrdinal -= times * symbol.weight;
    }
  }
  return aOrdinal == 0;
}

static bool DecimalToText(CounterValue aOrdinal, nsAString& aResult) {
  aResult.AppendInt(aOrdinal);
  return true;
}

// We know cjk-ideographic need 31 characters to display 99,999,999,999,999,999
// georgian needs 6 at most
// armenian needs 12 at most
// hebrew may need more...

#define NUM_BUF_SIZE 34

enum CJKIdeographicLang { CHINESE, KOREAN, JAPANESE };
struct CJKIdeographicData {
  char16_t digit[10];
  char16_t unit[3];
  char16_t unit10K[2];
  uint8_t lang;
  bool informal;
};
static const CJKIdeographicData gDataJapaneseInformal = {
    {0x3007, 0x4e00, 0x4e8c, 0x4e09, 0x56db, 0x4e94, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x5341, 0x767e, 0x5343},  // unit
    {0x4e07, 0x5104},          // unit10K
    JAPANESE,                  // lang
    true                       // informal
};
static const CJKIdeographicData gDataJapaneseFormal = {
    {0x96f6, 0x58f1, 0x5f10, 0x53c2, 0x56db, 0x4f0d, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x62fe, 0x767e, 0x9621},  // unit
    {0x842c, 0x5104},          // unit10K
    JAPANESE,                  // lang
    false                      // informal
};
static const CJKIdeographicData gDataKoreanHangulFormal = {
    {0xc601, 0xc77c, 0xc774, 0xc0bc, 0xc0ac, 0xc624, 0xc721, 0xce60, 0xd314,
     0xad6c},                  // digit
    {0xc2ed, 0xbc31, 0xcc9c},  // unit
    {0xb9cc, 0xc5b5},          // unit10K
    KOREAN,                    // lang
    false                      // informal
};
static const CJKIdeographicData gDataKoreanHanjaInformal = {
    {0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db, 0x4e94, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x5341, 0x767e, 0x5343},  // unit
    {0x842c, 0x5104},          // unit10K
    KOREAN,                    // lang
    true                       // informal
};
static const CJKIdeographicData gDataKoreanHanjaFormal = {
    {0x96f6, 0x58f9, 0x8cb3, 0x53c3, 0x56db, 0x4e94, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x62fe, 0x767e, 0x4edf},  // unit
    {0x842c, 0x5104},          // unit10K
    KOREAN,                    // lang
    false                      // informal
};
static const CJKIdeographicData gDataSimpChineseInformal = {
    {0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db, 0x4e94, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x5341, 0x767e, 0x5343},  // unit
    {0x4e07, 0x4ebf},          // unit10K
    CHINESE,                   // lang
    true                       // informal
};
static const CJKIdeographicData gDataSimpChineseFormal = {
    {0x96f6, 0x58f9, 0x8d30, 0x53c1, 0x8086, 0x4f0d, 0x9646, 0x67d2, 0x634c,
     0x7396},                  // digit
    {0x62fe, 0x4f70, 0x4edf},  // unit
    {0x4e07, 0x4ebf},          // unit10K
    CHINESE,                   // lang
    false                      // informal
};
static const CJKIdeographicData gDataTradChineseInformal = {
    {0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db, 0x4e94, 0x516d, 0x4e03, 0x516b,
     0x4e5d},                  // digit
    {0x5341, 0x767e, 0x5343},  // unit
    {0x842c, 0x5104},          // unit10K
    CHINESE,                   // lang
    true                       // informal
};
static const CJKIdeographicData gDataTradChineseFormal = {
    {0x96f6, 0x58f9, 0x8cb3, 0x53c3, 0x8086, 0x4f0d, 0x9678, 0x67d2, 0x634c,
     0x7396},                  // digit
    {0x62fe, 0x4f70, 0x4edf},  // unit
    {0x842c, 0x5104},          // unit10K
    CHINESE,                   // lang
    false                      // informal
};

static bool CJKIdeographicToText(CounterValue aOrdinal, nsAString& aResult,
                                 const CJKIdeographicData& data) {
  NS_ASSERTION(aOrdinal >= 0, "Only accept non-negative ordinal");
  char16_t buf[NUM_BUF_SIZE];
  int32_t idx = NUM_BUF_SIZE;
  int32_t pos = 0;
  bool needZero = (aOrdinal == 0);
  int32_t unitidx = 0, unit10Kidx = 0;
  do {
    unitidx = pos % 4;
    if (unitidx == 0) {
      unit10Kidx = pos / 4;
    }
    auto cur = static_cast<std::make_unsigned_t<CounterValue>>(aOrdinal) % 10;
    if (cur == 0) {
      if (needZero) {
        needZero = false;
        buf[--idx] = data.digit[0];
      }
    } else {
      if (data.lang == CHINESE) {
        needZero = true;
      }
      if (unit10Kidx != 0) {
        if (data.lang == KOREAN && idx != NUM_BUF_SIZE) {
          buf[--idx] = ' ';
        }
        buf[--idx] = data.unit10K[unit10Kidx - 1];
      }
      if (unitidx != 0) {
        buf[--idx] = data.unit[unitidx - 1];
      }
      if (cur != 1) {
        buf[--idx] = data.digit[cur];
      } else {
        bool needOne = true;
        if (data.informal) {
          switch (data.lang) {
            case CHINESE:
              if (unitidx == 1 &&
                  (aOrdinal == 1 || (pos > 4 && aOrdinal % 1000 == 1))) {
                needOne = false;
              }
              break;
            case JAPANESE:
              if (unitidx > 0 &&
                  (unitidx != 3 || (pos == 3 && aOrdinal == 1))) {
                needOne = false;
              }
              break;
            case KOREAN:
              if (unitidx > 0 || (pos == 4 && (aOrdinal % 1000) == 1)) {
                needOne = false;
              }
              break;
          }
        }
        if (needOne) {
          buf[--idx] = data.digit[1];
        }
      }
      unit10Kidx = 0;
    }
    aOrdinal /= 10;
    pos++;
  } while (aOrdinal > 0);
  aResult.Assign(buf + idx, NUM_BUF_SIZE - idx);
  return true;
}

#define HEBREW_GERESH 0x05F3
static const char16_t gHebrewDigit[22] = {
    //   1       2       3       4       5       6       7       8       9
    0x05D0, 0x05D1, 0x05D2, 0x05D3, 0x05D4, 0x05D5, 0x05D6, 0x05D7, 0x05D8,
    //  10      20      30      40      50      60      70      80      90
    0x05D9, 0x05DB, 0x05DC, 0x05DE, 0x05E0, 0x05E1, 0x05E2, 0x05E4, 0x05E6,
    // 100     200     300     400
    0x05E7, 0x05E8, 0x05E9, 0x05EA};

static bool HebrewToText(CounterValue aOrdinal, nsAString& aResult) {
  if (aOrdinal < 1 || aOrdinal > 999999) {
    return false;
  }

  bool outputSep = false;
  nsAutoString allText, thousandsGroup;
  do {
    thousandsGroup.Truncate();
    int32_t n3 = aOrdinal % 1000;
    // Process digit for 100 - 900
    for (int32_t n1 = 400; n1 > 0;) {
      if (n3 >= n1) {
        n3 -= n1;
        thousandsGroup.Append(gHebrewDigit[(n1 / 100) - 1 + 18]);
      } else {
        n1 -= 100;
      }  // if
    }    // for

    // Process digit for 10 - 90
    int32_t n2;
    if (n3 >= 10) {
      // Special process for 15 and 16
      if ((15 == n3) || (16 == n3)) {
        // Special rule for religious reason...
        // 15 is represented by 9 and 6, not 10 and 5
        // 16 is represented by 9 and 7, not 10 and 6
        n2 = 9;
        thousandsGroup.Append(gHebrewDigit[n2 - 1]);
      } else {
        n2 = n3 - (n3 % 10);
        thousandsGroup.Append(gHebrewDigit[(n2 / 10) - 1 + 9]);
      }  // if
      n3 -= n2;
    }  // if

    // Process digit for 1 - 9
    if (n3 > 0) thousandsGroup.Append(gHebrewDigit[n3 - 1]);
    if (outputSep) thousandsGroup.Append((char16_t)HEBREW_GERESH);
    if (allText.IsEmpty())
      allText = thousandsGroup;
    else
      allText = thousandsGroup + allText;
    aOrdinal /= 1000;
    outputSep = true;
  } while (aOrdinal >= 1);

  aResult = allText;
  return true;
}

// Convert ordinal to Ethiopic numeric representation.
// The detail is available at http://www.ethiopic.org/Numerals/
// The algorithm used here is based on the pseudo-code put up there by
// Daniel Yacob <yacob@geez.org>.
// Another reference is Unicode 3.0 standard section 11.1.
#define ETHIOPIC_ONE 0x1369
#define ETHIOPIC_TEN 0x1372
#define ETHIOPIC_HUNDRED 0x137B
#define ETHIOPIC_TEN_THOUSAND 0x137C

static bool EthiopicToText(CounterValue aOrdinal, nsAString& aResult) {
  if (aOrdinal < 1) {
    return false;
  }

  nsAutoString asciiNumberString;  // decimal string representation of ordinal
  DecimalToText(aOrdinal, asciiNumberString);
  uint8_t asciiStringLength = asciiNumberString.Length();

  // If number length is odd, add a leading "0"
  // the leading "0" preconditions the string to always have the
  // leading tens place populated, this avoids a check within the loop.
  // If we didn't add the leading "0", decrement asciiStringLength so
  // it will be equivalent to a zero-based index in both cases.
  if (asciiStringLength & 1) {
    asciiNumberString.InsertLiteral(u"0", 0);
  } else {
    asciiStringLength--;
  }

  aResult.Truncate();
  // Iterate from the highest digits to lowest
  // indexFromLeft       indexes digits (0 = most significant)
  // groupIndexFromRight indexes pairs of digits (0 = least significant)
  for (uint8_t indexFromLeft = 0, groupIndexFromRight = asciiStringLength >> 1;
       indexFromLeft <= asciiStringLength;
       indexFromLeft += 2, groupIndexFromRight--) {
    uint8_t tensValue = asciiNumberString.CharAt(indexFromLeft) & 0x0F;
    uint8_t unitsValue = asciiNumberString.CharAt(indexFromLeft + 1) & 0x0F;
    uint8_t groupValue = tensValue * 10 + unitsValue;

    bool oddGroup = (groupIndexFromRight & 1);

    // we want to clear ETHIOPIC_ONE when it is superfluous
    if (aOrdinal > 1 && groupValue == 1 &&  // one without a leading ten
        (oddGroup ||
         indexFromLeft == 0)) {  // preceding (100) or leading the sequence
      unitsValue = 0;
    }

    // put it all together...
    if (tensValue) {
      // map onto Ethiopic "tens":
      aResult.Append((char16_t)(tensValue + ETHIOPIC_TEN - 1));
    }
    if (unitsValue) {
      // map onto Ethiopic "units":
      aResult.Append((char16_t)(unitsValue + ETHIOPIC_ONE - 1));
    }
    // Add a separator for all even groups except the last,
    // and for odd groups with non-zero value.
    if (oddGroup) {
      if (groupValue) {
        aResult.Append((char16_t)ETHIOPIC_HUNDRED);
      }
    } else {
      if (groupIndexFromRight) {
        aResult.Append((char16_t)ETHIOPIC_TEN_THOUSAND);
      }
    }
  }
  return true;
}

static SpeakAs GetDefaultSpeakAsForSystem(StyleCounterSystem aSystem) {
  MOZ_ASSERT(aSystem != StyleCounterSystem::Extends,
             "Extends system does not have static default speak-as");
  switch (aSystem) {
    case StyleCounterSystem::Alphabetic:
      return SpeakAs::Spellout;
    case StyleCounterSystem::Cyclic:
      return SpeakAs::Bullets;
    default:
      return SpeakAs::Numbers;
  }
}

static bool SystemUsesNegativeSign(StyleCounterSystem aSystem) {
  MOZ_ASSERT(aSystem != StyleCounterSystem::Extends,
             "Cannot check this for extending style");
  switch (aSystem) {
    case StyleCounterSystem::Symbolic:
    case StyleCounterSystem::Alphabetic:
    case StyleCounterSystem::Numeric:
    case StyleCounterSystem::Additive:
      return true;
    default:
      return false;
  }
}

class BuiltinCounterStyle : public CounterStyle {
 public:
  constexpr BuiltinCounterStyle(int32_t aStyle, nsStaticAtom* aName)
      : CounterStyle(aStyle), mName(aName) {}

  nsStaticAtom* GetStyleName() const { return mName; }

  virtual void GetPrefix(nsAString& aResult) override;
  virtual void GetSuffix(nsAString& aResult) override;
  virtual void GetSpokenCounterText(CounterValue aOrdinal,
                                    WritingMode aWritingMode,
                                    nsAString& aResult,
                                    bool& aIsBullet) override;
  virtual bool IsBullet() override;

  virtual void GetNegative(NegativeType& aResult) override;
  virtual bool IsOrdinalInRange(CounterValue aOrdinal) override;
  virtual bool IsOrdinalInAutoRange(CounterValue aOrdinal) override;
  virtual void GetPad(PadType& aResult) override;
  virtual CounterStyle* GetFallback() override;
  virtual SpeakAs GetSpeakAs() override;
  virtual bool UseNegativeSign() override;

  virtual bool GetInitialCounterText(CounterValue aOrdinal,
                                     WritingMode aWritingMode,
                                     nsAString& aResult, bool& aIsRTL) override;

 protected:
  constexpr BuiltinCounterStyle(const BuiltinCounterStyle& aOther)
      : CounterStyle(aOther.mStyle), mName(aOther.mName) {}

 private:
  nsStaticAtom* mName;
};

/* virtual */
void BuiltinCounterStyle::GetPrefix(nsAString& aResult) { aResult.Truncate(); }

/* virtual */
void BuiltinCounterStyle::GetSuffix(nsAString& aResult) {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_NONE:
      aResult.Truncate();
      break;

    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
    case NS_STYLE_LIST_STYLE_ETHIOPIC_NUMERIC:
      aResult = ' ';
      break;

    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
      aResult = 0x3001;
      break;

    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
      aResult.AssignLiteral(u", ");
      break;

    default:
      aResult.AssignLiteral(u". ");
      break;
  }
}

static const char16_t kDiscCharacter = 0x2022;
static const char16_t kCircleCharacter = 0x25e6;
static const char16_t kSquareCharacter = 0x25fe;
static const char16_t kRightPointingCharacter = 0x25b8;
static const char16_t kLeftPointingCharacter = 0x25c2;
static const char16_t kDownPointingCharacter = 0x25be;

/* virtual */
void BuiltinCounterStyle::GetSpokenCounterText(CounterValue aOrdinal,
                                               WritingMode aWritingMode,
                                               nsAString& aResult,
                                               bool& aIsBullet) {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_NONE:
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN: {
      // Same as the initial representation
      bool isRTL;
      GetInitialCounterText(aOrdinal, aWritingMode, aResult, isRTL);
      aIsBullet = true;
      break;
    }
    default:
      CounterStyle::GetSpokenCounterText(aOrdinal, aWritingMode, aResult,
                                         aIsBullet);
      break;
  }
}

/* virtual */
bool BuiltinCounterStyle::IsBullet() {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
      return true;
    default:
      return false;
  }
}

static const char16_t gJapaneseNegative[] = {0x30de, 0x30a4, 0x30ca, 0x30b9,
                                             0x0000};
static const char16_t gKoreanNegative[] = {0xb9c8, 0xc774, 0xb108,
                                           0xc2a4, 0x0020, 0x0000};
static const char16_t gSimpChineseNegative[] = {0x8d1f, 0x0000};
static const char16_t gTradChineseNegative[] = {0x8ca0, 0x0000};

/* virtual */
void BuiltinCounterStyle::GetNegative(NegativeType& aResult) {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
      aResult.before = gJapaneseNegative;
      break;

    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
      aResult.before = gKoreanNegative;
      break;

    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
      aResult.before = gSimpChineseNegative;
      break;

    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
      aResult.before = gTradChineseNegative;
      break;

    default:
      aResult.before.AssignLiteral(u"-");
  }
  aResult.after.Truncate();
}

/* virtual */
bool BuiltinCounterStyle::IsOrdinalInRange(CounterValue aOrdinal) {
  switch (mStyle) {
    default:
    // cyclic
    case NS_STYLE_LIST_STYLE_NONE:
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
    // use DecimalToText
    case NS_STYLE_LIST_STYLE_DECIMAL:
    // use CJKIdeographicToText
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
      return true;

    // use EthiopicToText
    case NS_STYLE_LIST_STYLE_ETHIOPIC_NUMERIC:
      return aOrdinal >= 1;

    // use HebrewToText
    case NS_STYLE_LIST_STYLE_HEBREW:
      return aOrdinal >= 1 && aOrdinal <= 999999;
  }
}

/* virtual */
bool BuiltinCounterStyle::IsOrdinalInAutoRange(CounterValue aOrdinal) {
  switch (mStyle) {
    // cyclic:
    case NS_STYLE_LIST_STYLE_NONE:
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
    // numeric:
    case NS_STYLE_LIST_STYLE_DECIMAL:
      return true;

    // additive:
    case NS_STYLE_LIST_STYLE_HEBREW:
      return aOrdinal >= 0;

    // complex predefined:
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_ETHIOPIC_NUMERIC:
      return IsOrdinalInRange(aOrdinal);

    default:
      MOZ_ASSERT_UNREACHABLE("Unknown counter style");
      return false;
  }
}

/* virtual */
void BuiltinCounterStyle::GetPad(PadType& aResult) {
  aResult.width = 0;
  aResult.symbol.Truncate();
}

/* virtual */
CounterStyle* BuiltinCounterStyle::GetFallback() {
  // Fallback of dependent builtin counter styles are handled in class
  // DependentBuiltinCounterStyle.
  return CounterStyleManager::GetDecimalStyle();
}

/* virtual */
SpeakAs BuiltinCounterStyle::GetSpeakAs() {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_NONE:
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
      return SpeakAs::Bullets;
    default:
      return SpeakAs::Numbers;
  }
}

/* virtual */
bool BuiltinCounterStyle::UseNegativeSign() {
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_NONE:
    case NS_STYLE_LIST_STYLE_DISC:
    case NS_STYLE_LIST_STYLE_CIRCLE:
    case NS_STYLE_LIST_STYLE_SQUARE:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
      return false;
    default:
      return true;
  }
}

/* virtual */
bool BuiltinCounterStyle::GetInitialCounterText(CounterValue aOrdinal,
                                                WritingMode aWritingMode,
                                                nsAString& aResult,
                                                bool& aIsRTL) {
  aIsRTL = false;
  switch (mStyle) {
    // used by counters & extends counter-style code only
    // XXX We really need to do this the same way we do list bullets.
    case NS_STYLE_LIST_STYLE_NONE:
      aResult.Truncate();
      return true;
    case NS_STYLE_LIST_STYLE_DISC:
      aResult.Assign(kDiscCharacter);
      return true;
    case NS_STYLE_LIST_STYLE_CIRCLE:
      aResult.Assign(kCircleCharacter);
      return true;
    case NS_STYLE_LIST_STYLE_SQUARE:
      aResult.Assign(kSquareCharacter);
      return true;
    case NS_STYLE_LIST_STYLE_DISCLOSURE_CLOSED:
      if (aWritingMode.IsVertical()) {
        aResult.Assign(kDownPointingCharacter);
      } else if (aWritingMode.IsBidiLTR()) {
        aResult.Assign(kRightPointingCharacter);
      } else {
        aResult.Assign(kLeftPointingCharacter);
      }
      return true;
    case NS_STYLE_LIST_STYLE_DISCLOSURE_OPEN:
      if (!aWritingMode.IsVertical()) {
        aResult.Assign(kDownPointingCharacter);
      } else if (aWritingMode.IsVerticalLR()) {
        aResult.Assign(kRightPointingCharacter);
      } else {
        aResult.Assign(kLeftPointingCharacter);
      }
      return true;

    case NS_STYLE_LIST_STYLE_DECIMAL:
      return DecimalToText(aOrdinal, aResult);

    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataTradChineseInformal);
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataTradChineseFormal);
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataSimpChineseInformal);
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataSimpChineseFormal);
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataJapaneseInformal);
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataJapaneseFormal);
    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataKoreanHangulFormal);
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataKoreanHanjaInformal);
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
      return CJKIdeographicToText(aOrdinal, aResult, gDataKoreanHanjaFormal);

    case NS_STYLE_LIST_STYLE_HEBREW:
      aIsRTL = true;
      return HebrewToText(aOrdinal, aResult);

    case NS_STYLE_LIST_STYLE_ETHIOPIC_NUMERIC:
      return EthiopicToText(aOrdinal, aResult);

    default:
      MOZ_ASSERT_UNREACHABLE("Unknown builtin counter style");
      return false;
  }
}

static constexpr BuiltinCounterStyle gBuiltinStyleTable[] = {
#define BUILTIN_COUNTER_STYLE(value_, atom_) \
  {NS_STYLE_LIST_STYLE_##value_, nsGkAtoms::atom_},
#include "BuiltinCounterStyleList.h"
#undef BUILTIN_COUNTER_STYLE
};

#define BUILTIN_COUNTER_STYLE(value_, atom_)                                   \
  static_assert(gBuiltinStyleTable[NS_STYLE_LIST_STYLE_##value_].GetStyle() == \
                    NS_STYLE_LIST_STYLE_##value_,                              \
                "Builtin counter style " #atom_                                \
                " has unmatched index and value.");
#include "BuiltinCounterStyleList.h"
#undef BUILTIN_COUNTER_STYLE

class DependentBuiltinCounterStyle final : public BuiltinCounterStyle {
 public:
  DependentBuiltinCounterStyle(int32_t aStyle, CounterStyleManager* aManager)
      : BuiltinCounterStyle(gBuiltinStyleTable[aStyle]), mManager(aManager) {
    NS_ASSERTION(IsDependentStyle(), "Not a dependent builtin style");
    MOZ_ASSERT(!IsCustomStyle(), "Not a builtin style");
  }

  virtual CounterStyle* GetFallback() override;

  void* operator new(size_t sz, nsPresContext* aPresContext) {
    return aPresContext->PresShell()->AllocateByObjectID(
        eArenaObjectID_DependentBuiltinCounterStyle, sz);
  }

  void Destroy() {
    PresShell* presShell = mManager->PresContext()->PresShell();
    this->~DependentBuiltinCounterStyle();
    presShell->FreeByObjectID(eArenaObjectID_DependentBuiltinCounterStyle,
                              this);
  }

 private:
  ~DependentBuiltinCounterStyle() = default;

  CounterStyleManager* mManager;
};

/* virtual */
CounterStyle* DependentBuiltinCounterStyle::GetFallback() {
  switch (GetStyle()) {
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
      // These styles all have a larger range than cjk-decimal, so the
      // only case fallback is accessed is that they are extended.
      // Since extending styles will cache the data themselves, we need
      // not cache it here.
      return mManager->ResolveCounterStyle(nsGkAtoms::cjk_decimal);
    default:
      MOZ_ASSERT_UNREACHABLE("Not a valid dependent builtin style");
      return BuiltinCounterStyle::GetFallback();
  }
}

class CustomCounterStyle final : public CounterStyle {
 public:
  CustomCounterStyle(CounterStyleManager* aManager,
                     const RawServoCounterStyleRule* aRule)
      : CounterStyle(NS_STYLE_LIST_STYLE_CUSTOM),
        mManager(aManager),
        mRule(aRule),
        mRuleGeneration(Servo_CounterStyleRule_GetGeneration(aRule)),
        mSystem(Servo_CounterStyleRule_GetSystem(aRule)),
        mFlags(0),
        mFallback(nullptr),
        mSpeakAsCounter(nullptr),
        mExtends(nullptr),
        mExtendsRoot(nullptr) {}

  // This method will clear all cached data in the style and update the
  // generation number of the rule. It should be called when the rule of
  // this style is changed.
  void ResetCachedData();

  // This method will reset all cached data which may depend on other
  // counter style. It will reset all pointers to other counter styles.
  // For counter style extends other, in addition, all fields will be
  // reset to uninitialized state. This method should be called when any
  // other counter style is added, removed, or changed.
  void ResetDependentData();

  const RawServoCounterStyleRule* GetRule() const { return mRule; }
  uint32_t GetRuleGeneration() const { return mRuleGeneration; }

  virtual void GetPrefix(nsAString& aResult) override;
  virtual void GetSuffix(nsAString& aResult) override;
  virtual void GetSpokenCounterText(CounterValue aOrdinal,
                                    WritingMode aWritingMode,
                                    nsAString& aResult,
                                    bool& aIsBullet) override;
  virtual bool IsBullet() override;

  virtual void GetNegative(NegativeType& aResult) override;
  virtual bool IsOrdinalInRange(CounterValue aOrdinal) override;
  virtual bool IsOrdinalInAutoRange(CounterValue aOrdinal) override;
  virtual void GetPad(PadType& aResult) override;
  virtual CounterStyle* GetFallback() override;
  virtual SpeakAs GetSpeakAs() override;
  virtual bool UseNegativeSign() override;

  virtual void CallFallbackStyle(CounterValue aOrdinal,
                                 WritingMode aWritingMode, nsAString& aResult,
                                 bool& aIsRTL) override;
  virtual bool GetInitialCounterText(CounterValue aOrdinal,
                                     WritingMode aWritingMode,
                                     nsAString& aResult, bool& aIsRTL) override;

  bool IsExtendsSystem() { return mSystem == StyleCounterSystem::Extends; }

  void* operator new(size_t sz, nsPresContext* aPresContext) {
    return aPresContext->PresShell()->AllocateByObjectID(
        eArenaObjectID_CustomCounterStyle, sz);
  }

  void Destroy() {
    PresShell* presShell = mManager->PresContext()->PresShell();
    this->~CustomCounterStyle();
    presShell->FreeByObjectID(eArenaObjectID_CustomCounterStyle, this);
  }

 private:
  ~CustomCounterStyle() = default;

  Span<const nsString> GetSymbols();
  Span<const AdditiveSymbol> GetAdditiveSymbols();

  // The speak-as values of counter styles may form a loop, and the
  // loops may have complex interaction with the loop formed by
  // extending. To solve this problem, the computation of speak-as is
  // divided into two phases:
  // 1. figure out the raw value, by ComputeRawSpeakAs, and
  // 2. eliminate loop, by ComputeSpeakAs.
  // See comments before the definitions of these methods for details.
  SpeakAs GetSpeakAsAutoValue();
  void ComputeRawSpeakAs(SpeakAs& aSpeakAs, CounterStyle*& aSpeakAsCounter);
  CounterStyle* ComputeSpeakAs();

  CounterStyle* ComputeExtends();
  CounterStyle* GetExtends();
  CounterStyle* GetExtendsRoot();

  // CounterStyleManager should always overlive any CounterStyle as it
  // is owned by nsPresContext, and will be released after all nodes and
  // frames are released.
  CounterStyleManager* mManager;

  RefPtr<const RawServoCounterStyleRule> mRule;
  uint32_t mRuleGeneration;

  StyleCounterSystem mSystem;
  // GetSpeakAs will ensure that private member mSpeakAs is initialized before
  // used
  MOZ_INIT_OUTSIDE_CTOR SpeakAs mSpeakAs;

  enum {
    // loop detection
    FLAG_EXTENDS_VISITED = 1 << 0,
    FLAG_EXTENDS_LOOP = 1 << 1,
    FLAG_SPEAKAS_VISITED = 1 << 2,
    FLAG_SPEAKAS_LOOP = 1 << 3,
    // field status
    FLAG_NEGATIVE_INITED = 1 << 4,
    FLAG_PREFIX_INITED = 1 << 5,
    FLAG_SUFFIX_INITED = 1 << 6,
    FLAG_PAD_INITED = 1 << 7,
    FLAG_SPEAKAS_INITED = 1 << 8,
  };
  uint16_t mFlags;

  // Fields below will be initialized when necessary.
  StyleOwnedSlice<nsString> mSymbols;
  StyleOwnedSlice<AdditiveSymbol> mAdditiveSymbols;
  NegativeType mNegative;
  nsString mPrefix, mSuffix;
  PadType mPad;

  // CounterStyleManager will guarantee that none of the pointers below
  // refers to a freed CounterStyle. There are two possible cases where
  // the manager will release its reference to a CounterStyle: 1. the
  // manager itself is released, 2. a rule is invalidated. In the first
  // case, all counter style are removed from the manager, and should
  // also have been dereferenced from other objects. All styles will be
  // released all together. In the second case, CounterStyleManager::
  // NotifyRuleChanged will guarantee that all pointers will be reset
  // before any CounterStyle is released.

  CounterStyle* mFallback;
  // This field refers to the last counter in a speak-as chain.
  // That counter must not speak as another counter.
  CounterStyle* mSpeakAsCounter;

  CounterStyle* mExtends;
  // This field refers to the last counter in the extends chain. The
  // counter must be either a builtin style or a style whose system is
  // not 'extends'.
  CounterStyle* mExtendsRoot;
};

void CustomCounterStyle::ResetCachedData() {
  mSymbols.Clear();
  mAdditiveSymbols.Clear();
  mFlags &= ~(FLAG_NEGATIVE_INITED | FLAG_PREFIX_INITED | FLAG_SUFFIX_INITED |
              FLAG_PAD_INITED | FLAG_SPEAKAS_INITED);
  mFallback = nullptr;
  mSpeakAsCounter = nullptr;
  mExtends = nullptr;
  mExtendsRoot = nullptr;
  mRuleGeneration = Servo_CounterStyleRule_GetGeneration(mRule);
}

void CustomCounterStyle::ResetDependentData() {
  mFlags &= ~FLAG_SPEAKAS_INITED;
  mSpeakAsCounter = nullptr;
  mFallback = nullptr;
  mExtends = nullptr;
  mExtendsRoot = nullptr;
  if (IsExtendsSystem()) {
    mFlags &= ~(FLAG_NEGATIVE_INITED | FLAG_PREFIX_INITED | FLAG_SUFFIX_INITED |
                FLAG_PAD_INITED);
  }
}

/* virtual */
void CustomCounterStyle::GetPrefix(nsAString& aResult) {
  if (!(mFlags & FLAG_PREFIX_INITED)) {
    mFlags |= FLAG_PREFIX_INITED;

    if (!Servo_CounterStyleRule_GetPrefix(mRule, &mPrefix)) {
      if (IsExtendsSystem()) {
        GetExtends()->GetPrefix(mPrefix);
      } else {
        mPrefix.Truncate();
      }
    }
  }
  aResult = mPrefix;
}

/* virtual */
void CustomCounterStyle::GetSuffix(nsAString& aResult) {
  if (!(mFlags & FLAG_SUFFIX_INITED)) {
    mFlags |= FLAG_SUFFIX_INITED;

    if (!Servo_CounterStyleRule_GetSuffix(mRule, &mSuffix)) {
      if (IsExtendsSystem()) {
        GetExtends()->GetSuffix(mSuffix);
      } else {
        mSuffix.AssignLiteral(u". ");
      }
    }
  }
  aResult = mSuffix;
}

/* virtual */
void CustomCounterStyle::GetSpokenCounterText(CounterValue aOrdinal,
                                              WritingMode aWritingMode,
                                              nsAString& aResult,
                                              bool& aIsBullet) {
  if (GetSpeakAs() != SpeakAs::Other) {
    CounterStyle::GetSpokenCounterText(aOrdinal, aWritingMode, aResult,
                                       aIsBullet);
  } else {
    MOZ_ASSERT(mSpeakAsCounter,
               "mSpeakAsCounter should have been initialized.");
    mSpeakAsCounter->GetSpokenCounterText(aOrdinal, aWritingMode, aResult,
                                          aIsBullet);
  }
}

/* virtual */
bool CustomCounterStyle::IsBullet() {
  switch (mSystem) {
    case StyleCounterSystem::Cyclic:
      // Only use ::-moz-list-bullet for cyclic system
      return true;
    case StyleCounterSystem::Extends:
      return GetExtendsRoot()->IsBullet();
    default:
      return false;
  }
}

/* virtual */
void CustomCounterStyle::GetNegative(NegativeType& aResult) {
  if (!(mFlags & FLAG_NEGATIVE_INITED)) {
    mFlags |= FLAG_NEGATIVE_INITED;
    if (!Servo_CounterStyleRule_GetNegative(mRule, &mNegative.before,
                                            &mNegative.after)) {
      if (IsExtendsSystem()) {
        GetExtends()->GetNegative(mNegative);
      } else {
        mNegative.before.AssignLiteral(u"-");
        mNegative.after.Truncate();
      }
    }
  }
  aResult = mNegative;
}

/* virtual */
bool CustomCounterStyle::IsOrdinalInRange(CounterValue aOrdinal) {
  auto inRange = Servo_CounterStyleRule_IsInRange(mRule, aOrdinal);
  switch (inRange) {
    case StyleIsOrdinalInRange::InRange:
      return true;
    case StyleIsOrdinalInRange::NotInRange:
      return false;
    case StyleIsOrdinalInRange::NoOrdinalSpecified:
      if (IsExtendsSystem()) {
        return GetExtends()->IsOrdinalInRange(aOrdinal);
      }
      break;
    case StyleIsOrdinalInRange::Auto:
      break;
    default:
      MOZ_ASSERT_UNREACHABLE("Unkown result from IsInRange?");
  }
  return IsOrdinalInAutoRange(aOrdinal);
}

/* virtual */
bool CustomCounterStyle::IsOrdinalInAutoRange(CounterValue aOrdinal) {
  switch (mSystem) {
    case StyleCounterSystem::Cyclic:
    case StyleCounterSystem::Numeric:
    case StyleCounterSystem::Fixed:
      return true;
    case StyleCounterSystem::Alphabetic:
    case StyleCounterSystem::Symbolic:
      return aOrdinal >= 1;
    case StyleCounterSystem::Additive:
      return aOrdinal >= 0;
    case StyleCounterSystem::Extends:
      return GetExtendsRoot()->IsOrdinalInAutoRange(aOrdinal);
    default:
      MOZ_ASSERT_UNREACHABLE("Invalid system for computing auto value.");
      return false;
  }
}

/* virtual */
void CustomCounterStyle::GetPad(PadType& aResult) {
  if (!(mFlags & FLAG_PAD_INITED)) {
    mFlags |= FLAG_PAD_INITED;
    if (!Servo_CounterStyleRule_GetPad(mRule, &mPad.width, &mPad.symbol)) {
      if (IsExtendsSystem()) {
        GetExtends()->GetPad(mPad);
      } else {
        mPad.width = 0;
        mPad.symbol.Truncate();
      }
    }
  }
  aResult = mPad;
}

/* virtual */
CounterStyle* CustomCounterStyle::GetFallback() {
  if (!mFallback) {
    mFallback = CounterStyleManager::GetDecimalStyle();
    if (nsAtom* fallback = Servo_CounterStyleRule_GetFallback(mRule)) {
      mFallback = mManager->ResolveCounterStyle(fallback);
    } else if (IsExtendsSystem()) {
      mFallback = GetExtends()->GetFallback();
    }
  }
  return mFallback;
}

/* virtual */
SpeakAs CustomCounterStyle::GetSpeakAs() {
  if (!(mFlags & FLAG_SPEAKAS_INITED)) {
    ComputeSpeakAs();
  }
  return mSpeakAs;
}

/* virtual */
bool CustomCounterStyle::UseNegativeSign() {
  if (mSystem == StyleCounterSystem::Extends) {
    return GetExtendsRoot()->UseNegativeSign();
  }
  return SystemUsesNegativeSign(mSystem);
}

/* virtual */
void CustomCounterStyle::CallFallbackStyle(CounterValue aOrdinal,
                                           WritingMode aWritingMode,
                                           nsAString& aResult, bool& aIsRTL) {
  CounterStyle* fallback = GetFallback();
  // If it recursively falls back to this counter style again,
  // it will then fallback to decimal to break the loop.
  mFallback = CounterStyleManager::GetDecimalStyle();
  fallback->GetCounterText(aOrdinal, aWritingMode, aResult, aIsRTL);
  mFallback = fallback;
}

/* virtual */
bool CustomCounterStyle::GetInitialCounterText(CounterValue aOrdinal,
                                               WritingMode aWritingMode,
                                               nsAString& aResult,
                                               bool& aIsRTL) {
  switch (mSystem) {
    case StyleCounterSystem::Cyclic:
      return GetCyclicCounterText(aOrdinal, aResult, GetSymbols());
    case StyleCounterSystem::Fixed: {
      int32_t start = Servo_CounterStyleRule_GetFixedFirstValue(mRule);
      return GetFixedCounterText(aOrdinal, aResult, start, GetSymbols());
    }
    case StyleCounterSystem::Symbolic:
      return GetSymbolicCounterText(aOrdinal, aResult, GetSymbols());
    case StyleCounterSystem::Alphabetic:
      return GetAlphabeticCounterText(aOrdinal, aResult, GetSymbols());
    case StyleCounterSystem::Numeric:
      return GetNumericCounterText(aOrdinal, aResult, GetSymbols());
    case StyleCounterSystem::Additive:
      return GetAdditiveCounterText(aOrdinal, aResult, GetAdditiveSymbols());
    case StyleCounterSystem::Extends:
      return GetExtendsRoot()->GetInitialCounterText(aOrdinal, aWritingMode,
                                                     aResult, aIsRTL);
    default:
      MOZ_ASSERT_UNREACHABLE("Invalid system.");
      return false;
  }
}

Span<const nsString> CustomCounterStyle::GetSymbols() {
  if (mSymbols.IsEmpty()) {
    Servo_CounterStyleRule_GetSymbols(mRule, &mSymbols);
  }
  return mSymbols.AsSpan();
}

Span<const AdditiveSymbol> CustomCounterStyle::GetAdditiveSymbols() {
  if (mAdditiveSymbols.IsEmpty()) {
    Servo_CounterStyleRule_GetAdditiveSymbols(mRule, &mAdditiveSymbols);
  }
  return mAdditiveSymbols.AsSpan();
}

// This method is used to provide the computed value for 'auto'.
SpeakAs CustomCounterStyle::GetSpeakAsAutoValue() {
  auto system = mSystem;
  if (IsExtendsSystem()) {
    CounterStyle* root = GetExtendsRoot();
    if (!root->IsCustomStyle()) {
      // It is safe to call GetSpeakAs on non-custom style.
      return root->GetSpeakAs();
    }
    system = static_cast<CustomCounterStyle*>(root)->mSystem;
  }
  return GetDefaultSpeakAsForSystem(system);
}

// This method corresponds to the first stage of computation of the
// value of speak-as. It will extract the value from the rule and
// possibly recursively call itself on the extended style to figure
// out the raw value. To keep things clear, this method is designed to
// have no side effects (but functions it calls may still affect other
// fields in the style.)
void CustomCounterStyle::ComputeRawSpeakAs(SpeakAs& aSpeakAs,
                                           CounterStyle*& aSpeakAsCounter) {
  NS_ASSERTION(!(mFlags & FLAG_SPEAKAS_INITED),
               "ComputeRawSpeakAs is called with speak-as inited.");

  auto speakAs = StyleCounterSpeakAs::None();
  Servo_CounterStyleRule_GetSpeakAs(mRule, &speakAs);
  switch (speakAs.tag) {
    case StyleCounterSpeakAs::Tag::Auto:
      aSpeakAs = GetSpeakAsAutoValue();
      break;
    case StyleCounterSpeakAs::Tag::Bullets:
      aSpeakAs = SpeakAs::Bullets;
      break;
    case StyleCounterSpeakAs::Tag::Numbers:
      aSpeakAs = SpeakAs::Numbers;
      break;
    case StyleCounterSpeakAs::Tag::Words:
      aSpeakAs = SpeakAs::Words;
      break;
    case StyleCounterSpeakAs::Tag::Ident:
      aSpeakAs = SpeakAs::Other;
      aSpeakAsCounter = mManager->ResolveCounterStyle(speakAs.AsIdent());
      break;
    case StyleCounterSpeakAs::Tag::None: {
      if (!IsExtendsSystem()) {
        aSpeakAs = GetSpeakAsAutoValue();
      } else {
        CounterStyle* extended = GetExtends();
        if (!extended->IsCustomStyle()) {
          // It is safe to call GetSpeakAs on non-custom style.
          aSpeakAs = extended->GetSpeakAs();
        } else {
          CustomCounterStyle* custom =
              static_cast<CustomCounterStyle*>(extended);
          if (!(custom->mFlags & FLAG_SPEAKAS_INITED)) {
            custom->ComputeRawSpeakAs(aSpeakAs, aSpeakAsCounter);
          } else {
            aSpeakAs = custom->mSpeakAs;
            aSpeakAsCounter = custom->mSpeakAsCounter;
          }
        }
      }
      break;
    }
    default:
      MOZ_ASSERT_UNREACHABLE("Invalid speak-as value");
  }
}

// This method corresponds to the second stage of getting speak-as
// related values. It will recursively figure out the final value of
// mSpeakAs and mSpeakAsCounter. This method returns nullptr if the
// caller is in a loop, and the root counter style in the chain
// otherwise. It use the same loop detection algorithm as
// CustomCounterStyle::ComputeExtends, see comments before that
// method for more details.
CounterStyle* CustomCounterStyle::ComputeSpeakAs() {
  if (mFlags & FLAG_SPEAKAS_INITED) {
    if (mSpeakAs == SpeakAs::Other) {
      return mSpeakAsCounter;
    }
    return this;
  }

  if (mFlags & FLAG_SPEAKAS_VISITED) {
    // loop detected
    mFlags |= FLAG_SPEAKAS_LOOP;
    return nullptr;
  }

  CounterStyle* speakAsCounter;
  ComputeRawSpeakAs(mSpeakAs, speakAsCounter);

  bool inLoop = false;
  if (mSpeakAs != SpeakAs::Other) {
    mSpeakAsCounter = nullptr;
  } else if (!speakAsCounter->IsCustomStyle()) {
    mSpeakAsCounter = speakAsCounter;
  } else {
    mFlags |= FLAG_SPEAKAS_VISITED;
    CounterStyle* target =
        static_cast<CustomCounterStyle*>(speakAsCounter)->ComputeSpeakAs();
    mFlags &= ~FLAG_SPEAKAS_VISITED;

    if (target) {
      NS_ASSERTION(!(mFlags & FLAG_SPEAKAS_LOOP),
                   "Invalid state for speak-as loop detecting");
      mSpeakAsCounter = target;
    } else {
      mSpeakAs = GetSpeakAsAutoValue();
      mSpeakAsCounter = nullptr;
      if (mFlags & FLAG_SPEAKAS_LOOP) {
        mFlags &= ~FLAG_SPEAKAS_LOOP;
      } else {
        inLoop = true;
      }
    }
  }

  mFlags |= FLAG_SPEAKAS_INITED;
  if (inLoop) {
    return nullptr;
  }
  return mSpeakAsCounter ? mSpeakAsCounter : this;
}

// This method will recursively figure out mExtends in the whole chain.
// It will return nullptr if the caller is in a loop, and return this
// otherwise. To detect the loop, this method marks the style VISITED
// before the recursive call. When a VISITED style is reached again, the
// loop is detected, and flag LOOP will be marked on the first style in
// loop. mExtends of all counter styles in loop will be set to decimal
// according to the spec.
CounterStyle* CustomCounterStyle::ComputeExtends() {
  if (!IsExtendsSystem() || mExtends) {
    return this;
  }
  if (mFlags & FLAG_EXTENDS_VISITED) {
    // loop detected
    mFlags |= FLAG_EXTENDS_LOOP;
    return nullptr;
  }

  nsAtom* extended = Servo_CounterStyleRule_GetExtended(mRule);
  CounterStyle* nextCounter = mManager->ResolveCounterStyle(extended);
  CounterStyle* target = nextCounter;
  if (nextCounter->IsCustomStyle()) {
    mFlags |= FLAG_EXTENDS_VISITED;
    target = static_cast<CustomCounterStyle*>(nextCounter)->ComputeExtends();
    mFlags &= ~FLAG_EXTENDS_VISITED;
  }

  if (target) {
    NS_ASSERTION(!(mFlags & FLAG_EXTENDS_LOOP),
                 "Invalid state for extends loop detecting");
    mExtends = nextCounter;
    return this;
  } else {
    mExtends = CounterStyleManager::GetDecimalStyle();
    if (mFlags & FLAG_EXTENDS_LOOP) {
      mFlags &= ~FLAG_EXTENDS_LOOP;
      return this;
    } else {
      return nullptr;
    }
  }
}

CounterStyle* CustomCounterStyle::GetExtends() {
  if (!mExtends) {
    // Any extends loop will be eliminated in the method below.
    ComputeExtends();
  }
  return mExtends;
}

CounterStyle* CustomCounterStyle::GetExtendsRoot() {
  if (!mExtendsRoot) {
    CounterStyle* extended = GetExtends();
    mExtendsRoot = extended;
    if (extended->IsCustomStyle()) {
      CustomCounterStyle* custom = static_cast<CustomCounterStyle*>(extended);
      if (custom->IsExtendsSystem()) {
        // This will make mExtendsRoot in the whole extends chain be
        // set recursively, which could save work when part of a chain
        // is shared by multiple counter styles.
        mExtendsRoot = custom->GetExtendsRoot();
      }
    }
  }
  return mExtendsRoot;
}

AnonymousCounterStyle::AnonymousCounterStyle(const nsAString& aContent)
    : CounterStyle(NS_STYLE_LIST_STYLE_CUSTOM),
      mSingleString(true),
      mSymbolsType(StyleSymbolsType::Cyclic) {
  mSymbols.SetCapacity(1);
  mSymbols.AppendElement(aContent);
}

AnonymousCounterStyle::AnonymousCounterStyle(StyleSymbolsType aType,
                                             nsTArray<nsString> aSymbols)
    : CounterStyle(NS_STYLE_LIST_STYLE_CUSTOM),
      mSingleString(false),
      mSymbolsType(aType),
      mSymbols(std::move(aSymbols)) {}

/* virtual */
void AnonymousCounterStyle::GetPrefix(nsAString& aResult) {
  aResult.Truncate();
}

/* virtual */
void AnonymousCounterStyle::GetSuffix(nsAString& aResult) {
  if (IsSingleString()) {
    aResult.Truncate();
  } else {
    aResult = ' ';
  }
}

/* virtual */
bool AnonymousCounterStyle::IsBullet() {
  // Only use ::-moz-list-bullet for cyclic system
  return mSymbolsType == StyleSymbolsType::Cyclic;
}

/* virtual */
void AnonymousCounterStyle::GetNegative(NegativeType& aResult) {
  aResult.before.AssignLiteral(u"-");
  aResult.after.Truncate();
}

/* virtual */
bool AnonymousCounterStyle::IsOrdinalInRange(CounterValue aOrdinal) {
  switch (mSymbolsType) {
    case StyleSymbolsType::Cyclic:
    case StyleSymbolsType::Numeric:
    case StyleSymbolsType::Fixed:
      return true;
    case StyleSymbolsType::Alphabetic:
    case StyleSymbolsType::Symbolic:
      return aOrdinal >= 1;
    default:
      MOZ_ASSERT_UNREACHABLE("Invalid system.");
      return false;
  }
}

/* virtual */
bool AnonymousCounterStyle::IsOrdinalInAutoRange(CounterValue aOrdinal) {
  return AnonymousCounterStyle::IsOrdinalInRange(aOrdinal);
}

/* virtual */
void AnonymousCounterStyle::GetPad(PadType& aResult) {
  aResult.width = 0;
  aResult.symbol.Truncate();
}

/* virtual */
CounterStyle* AnonymousCounterStyle::GetFallback() {
  return CounterStyleManager::GetDecimalStyle();
}

StyleCounterSystem AnonymousCounterStyle::GetSystem() const {
  switch (mSymbolsType) {
    case StyleSymbolsType::Cyclic:
      return StyleCounterSystem::Cyclic;
    case StyleSymbolsType::Numeric:
      return StyleCounterSystem::Numeric;
    case StyleSymbolsType::Fixed:
      return StyleCounterSystem::Fixed;
    case StyleSymbolsType::Alphabetic:
      return StyleCounterSystem::Alphabetic;
    case StyleSymbolsType::Symbolic:
      return StyleCounterSystem::Symbolic;
  }
  MOZ_ASSERT_UNREACHABLE("Unknown symbols() type");
  return StyleCounterSystem::Cyclic;
}

/* virtual */
SpeakAs AnonymousCounterStyle::GetSpeakAs() {
  return GetDefaultSpeakAsForSystem(GetSystem());
}

/* virtual */
bool AnonymousCounterStyle::UseNegativeSign() {
  return SystemUsesNegativeSign(GetSystem());
}

/* virtual */
bool AnonymousCounterStyle::GetInitialCounterText(CounterValue aOrdinal,
                                                  WritingMode aWritingMode,
                                                  nsAString& aResult,
                                                  bool& aIsRTL) {
  switch (mSymbolsType) {
    case StyleSymbolsType::Cyclic:
      return GetCyclicCounterText(aOrdinal, aResult, mSymbols);
    case StyleSymbolsType::Numeric:
      return GetNumericCounterText(aOrdinal, aResult, mSymbols);
    case StyleSymbolsType::Fixed:
      return GetFixedCounterText(aOrdinal, aResult, 1, mSymbols);
    case StyleSymbolsType::Alphabetic:
      return GetAlphabeticCounterText(aOrdinal, aResult, mSymbols);
    case StyleSymbolsType::Symbolic:
      return GetSymbolicCounterText(aOrdinal, aResult, mSymbols);
  }
  MOZ_ASSERT_UNREACHABLE("Invalid system.");
  return false;
}

bool CounterStyle::IsDependentStyle() const {
  switch (mStyle) {
    // CustomCounterStyle
    case NS_STYLE_LIST_STYLE_CUSTOM:
    // DependentBuiltinCounterStyle
    case NS_STYLE_LIST_STYLE_JAPANESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_JAPANESE_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANGUL_FORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_INFORMAL:
    case NS_STYLE_LIST_STYLE_KOREAN_HANJA_FORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_SIMP_CHINESE_FORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_INFORMAL:
    case NS_STYLE_LIST_STYLE_TRAD_CHINESE_FORMAL:
      return true;

    // BuiltinCounterStyle
    default:
      return false;
  }
}

void CounterStyle::GetCounterText(CounterValue aOrdinal,
                                  WritingMode aWritingMode, nsAString& aResult,
                                  bool& aIsRTL) {
  bool success = IsOrdinalInRange(aOrdinal);
  aIsRTL = false;

  if (success) {
    // generate initial representation
    bool useNegativeSign = UseNegativeSign();
    nsAutoString initialText;
    CounterValue ordinal;
    if (!useNegativeSign) {
      ordinal = aOrdinal;
    } else {
      CheckedInt<CounterValue> absolute(Abs(aOrdinal));
      ordinal = absolute.isValid() ? absolute.value()
                                   : std::numeric_limits<CounterValue>::max();
    }
    success = GetInitialCounterText(ordinal, aWritingMode, initialText, aIsRTL);

    // add pad & negative, build the final result
    if (success) {
      PadType pad;
      GetPad(pad);
      // We have to calculate the difference here since suffix part of negative
      // sign may be appended to initialText later.
      int32_t diff = pad.width - unicode::CountGraphemeClusters(
                                     initialText.Data(), initialText.Length());
      aResult.Truncate();
      if (useNegativeSign && aOrdinal < 0) {
        NegativeType negative;
        GetNegative(negative);
        aResult.Append(negative.before);
        // There is nothing between the suffix part of negative and initial
        // representation, so we append it directly here.
        initialText.Append(negative.after);
      }
      if (diff > 0) {
        auto length = pad.symbol.Length();
        if (diff > LENGTH_LIMIT || length > LENGTH_LIMIT ||
            diff * length > LENGTH_LIMIT) {
          success = false;
        } else if (length > 0) {
          for (int32_t i = 0; i < diff; ++i) {
            aResult.Append(pad.symbol);
          }
        }
      }
      if (success) {
        aResult.Append(initialText);
      }
    }
  }

  if (!success) {
    CallFallbackStyle(aOrdinal, aWritingMode, aResult, aIsRTL);
  }
}

/* virtual */
void CounterStyle::GetSpokenCounterText(CounterValue aOrdinal,
                                        WritingMode aWritingMode,
                                        nsAString& aResult, bool& aIsBullet) {
  bool isRTL;  // we don't care about direction for spoken text
  aIsBullet = false;
  switch (GetSpeakAs()) {
    case SpeakAs::Bullets:
      aResult.Assign(kDiscCharacter);
      aIsBullet = true;
      break;
    case SpeakAs::Numbers:
      DecimalToText(aOrdinal, aResult);
      break;
    case SpeakAs::Spellout:
      // we currently do not actually support 'spell-out',
      // so 'words' is used instead.
    case SpeakAs::Words:
      GetCounterText(aOrdinal, WritingMode(), aResult, isRTL);
      break;
    case SpeakAs::Other:
      // This should be processed by CustomCounterStyle
      MOZ_ASSERT_UNREACHABLE("Invalid speak-as value");
      break;
    default:
      MOZ_ASSERT_UNREACHABLE("Unknown speak-as value");
      break;
  }
}

/* virtual */
void CounterStyle::CallFallbackStyle(CounterValue aOrdinal,
                                     WritingMode aWritingMode,
                                     nsAString& aResult, bool& aIsRTL) {
  GetFallback()->GetCounterText(aOrdinal, aWritingMode, aResult, aIsRTL);
}

CounterStyleManager::CounterStyleManager(nsPresContext* aPresContext)
    : mPresContext(aPresContext) {
  // Insert the static styles into cache table
  mStyles.Put(nsGkAtoms::none, GetNoneStyle());
  mStyles.Put(nsGkAtoms::decimal, GetDecimalStyle());
  mStyles.Put(nsGkAtoms::disc, GetDiscStyle());
}

CounterStyleManager::~CounterStyleManager() {
  MOZ_ASSERT(!mPresContext, "Disconnect should have been called");
}

void CounterStyleManager::DestroyCounterStyle(CounterStyle* aCounterStyle) {
  if (aCounterStyle->IsCustomStyle()) {
    MOZ_ASSERT(!aCounterStyle->AsAnonymous(),
               "Anonymous counter styles "
               "are not managed by CounterStyleManager");
    static_cast<CustomCounterStyle*>(aCounterStyle)->Destroy();
  } else if (aCounterStyle->IsDependentStyle()) {
    static_cast<DependentBuiltinCounterStyle*>(aCounterStyle)->Destroy();
  } else {
    MOZ_ASSERT_UNREACHABLE("Builtin counter styles should not be destroyed");
  }
}

void CounterStyleManager::Disconnect() {
  CleanRetiredStyles();
  for (auto iter = mStyles.Iter(); !iter.Done(); iter.Next()) {
    CounterStyle* style = iter.Data();
    if (style->IsDependentStyle()) {
      DestroyCounterStyle(style);
    }
  }
  mStyles.Clear();
  mPresContext = nullptr;
}

CounterStyle* CounterStyleManager::ResolveCounterStyle(nsAtom* aName) {
  MOZ_ASSERT(NS_IsMainThread());
  CounterStyle* data = GetCounterStyle(aName);
  if (data) {
    return data;
  }

  // Names are compared case-sensitively here. Predefined names should
  // have been lowercased by the parser.
  ServoStyleSet* styleSet = mPresContext->StyleSet();
  auto* rule = styleSet->CounterStyleRuleForName(aName);
  if (rule) {
    MOZ_ASSERT(Servo_CounterStyleRule_GetName(rule) == aName);
    data = new (mPresContext) CustomCounterStyle(this, rule);
  } else {
    for (const BuiltinCounterStyle& item : gBuiltinStyleTable) {
      if (item.GetStyleName() == aName) {
        int32_t style = item.GetStyle();
        data = item.IsDependentStyle()
                   ? new (mPresContext)
                         DependentBuiltinCounterStyle(style, this)
                   : GetBuiltinStyle(style);
        break;
      }
    }
  }
  if (!data) {
    data = GetDecimalStyle();
  }
  mStyles.Put(aName, data);
  return data;
}

/* static */
CounterStyle* CounterStyleManager::GetBuiltinStyle(int32_t aStyle) {
  MOZ_ASSERT(0 <= aStyle && size_t(aStyle) < sizeof(gBuiltinStyleTable),
             "Require a valid builtin style constant");
  MOZ_ASSERT(!gBuiltinStyleTable[aStyle].IsDependentStyle(),
             "Cannot get dependent builtin style");
  // No method of BuiltinCounterStyle mutates the struct itself, so it
  // should be fine to cast const away.
  return const_cast<BuiltinCounterStyle*>(&gBuiltinStyleTable[aStyle]);
}

bool CounterStyleManager::NotifyRuleChanged() {
  bool changed = false;
  for (auto iter = mStyles.Iter(); !iter.Done(); iter.Next()) {
    CounterStyle* style = iter.Data();
    bool toBeUpdated = false;
    bool toBeRemoved = false;
    ServoStyleSet* styleSet = mPresContext->StyleSet();
    auto* newRule = styleSet->CounterStyleRuleForName(iter.Key());
    if (!newRule) {
      if (style->IsCustomStyle()) {
        toBeRemoved = true;
      }
    } else {
      if (!style->IsCustomStyle()) {
        toBeRemoved = true;
      } else {
        auto custom = static_cast<CustomCounterStyle*>(style);
        if (custom->GetRule() != newRule) {
          toBeRemoved = true;
        } else {
          auto generation = Servo_CounterStyleRule_GetGeneration(newRule);
          if (custom->GetRuleGeneration() != generation) {
            toBeUpdated = true;
            custom->ResetCachedData();
          }
        }
      }
    }
    changed = changed || toBeUpdated || toBeRemoved;
    if (toBeRemoved) {
      if (style->IsDependentStyle()) {
        // Add object to retired list so we can clean them up later.
        mRetiredStyles.AppendElement(style);
      }
      iter.Remove();
    }
  }

  if (changed) {
    for (auto iter = mStyles.Iter(); !iter.Done(); iter.Next()) {
      CounterStyle* style = iter.Data();
      if (style->IsCustomStyle()) {
        CustomCounterStyle* custom = static_cast<CustomCounterStyle*>(style);
        custom->ResetDependentData();
      }
      // There is no dependent data cached in DependentBuiltinCounterStyle
      // instances, so we don't need to reset their data.
    }
  }
  return changed;
}

void CounterStyleManager::CleanRetiredStyles() {
  nsTArray<CounterStyle*> list(std::move(mRetiredStyles));
  for (CounterStyle* style : list) {
    DestroyCounterStyle(style);
  }
}

}  // namespace mozilla