layout/style/CounterStyleManager.cpp
author Xidorn Quan <quanxunzhen@gmail.com>
Wed, 11 Jun 2014 21:13:00 -0400
changeset 188318 6576396848f105936ace359d046a4b7d985b7861
parent 188317 bffb0b2f7c2f279ba10d407fb302e00c2051364f
child 188824 9603399b9ee1a95a7e2359d3c878e41cc6012ed2
permissions -rw-r--r--
Bug 966166 - Part 5: Move computation code with minor changes. r=dbaron In addition to moving the code, this patch also: * changes the square character from U+25AA to U+25FE to match the spec * changes all the generating functions from using append to using assign * removes negative handling from CJKIdeographicToText since it is no longer used there * fixes indentation and naming conventions * changes buffer size in DecimalToText

/* -*- 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 "mozilla/Types.h"
#include "mozilla/CheckedInt.h"
#include "mozilla/MathAlgorithms.h"
#include "mozilla/ArrayUtils.h"
#include "prprf.h"
#include "nsString.h"
#include "nsStyleSet.h"
#include "nsCSSRules.h"
#include "nsTArray.h"
#include "nsTHashtable.h"
#include "nsUnicodeProperties.h"

namespace mozilla {

struct AdditiveSymbol
{
  CounterValue weight;
  nsString symbol;
};

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,
                     nsSubstring& aResult,
                     const nsTArray<nsString>& aSymbols)
{
  NS_ABORT_IF_FALSE(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,
                    nsSubstring& aResult,
                    CounterValue aStart,
                    const nsTArray<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,
                       nsSubstring& aResult,
                       const nsTArray<nsString>& aSymbols)
{
  NS_ABORT_IF_FALSE(aSymbols.Length() >= 1,
                    "No symbol available for symbolic counter.");
  NS_ABORT_IF_FALSE(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,
                         nsSubstring& aResult,
                         const nsTArray<nsString>& aSymbols)
{
  NS_ABORT_IF_FALSE(aSymbols.Length() >= 2,
                    "Too few symbols for alphabetic counter.");
  NS_ABORT_IF_FALSE(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.
  nsAutoTArray<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,
                      nsSubstring& aResult,
                      const nsTArray<nsString>& aSymbols)
{
  NS_ABORT_IF_FALSE(aSymbols.Length() >= 2,
                    "Too few symbols for numeric counter.");
  NS_ABORT_IF_FALSE(aOrdinal >= 0, "Invalid ordinal.");

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

  auto n = aSymbols.Length();
  nsAutoTArray<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,
                       nsSubstring& aResult,
                       const nsTArray<AdditiveSymbol>& aSymbols)
{
  NS_ABORT_IF_FALSE(aOrdinal >= 0, "Invalid ordinal.");

  if (aOrdinal == 0) {
    const AdditiveSymbol& last = aSymbols.LastElement();
    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, nsSubstring& aResult)
{
  // 3 for additional digit, negative sign, and null
  char cbuf[std::numeric_limits<CounterValue>::digits10 + 3];
  PR_snprintf(cbuf, sizeof(cbuf), "%ld", aOrdinal);
  aResult.AssignASCII(cbuf);
  return true;
}

static bool
TamilToText(CounterValue aOrdinal, nsSubstring& aResult)
{
  if (aOrdinal < 1 || aOrdinal > 9999) {
    return false;
  }
  char16_t diff = 0x0BE6 - char16_t('0');
  // We're going to be appending to whatever is in "result" already, so make
  // sure to only munge the new bits.  Note that we can't just grab the pointer
  // to the new stuff here, since appending to the string can realloc.
  DecimalToText(aOrdinal, aResult);
  char16_t* p = aResult.BeginWriting();
  for(; '\0' != *p ; p++) 
    if(*p != char16_t('0'))
      *p += diff;
  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 = {
  {                           // digit
    0x3007, 0x4e00, 0x4e8c, 0x4e09, 0x56db,
    0x4e94, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x5341, 0x767e, 0x5343 }, // unit
  { 0x4e07, 0x5104 },         // unit10K
  JAPANESE,                   // lang
  true                        // informal
};
static const CJKIdeographicData gDataJapaneseFormal = {
  {                           // digit
    0x96f6, 0x58f1, 0x5f10, 0x53c2, 0x56db,
    0x4f0d, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x62fe, 0x767e, 0x9621 }, // unit
  { 0x842c, 0x5104 },         // unit10K
  JAPANESE,                   // lang
  false                       // informal
};
static const CJKIdeographicData gDataKoreanHangulFormal = {
  {                           // digit
    0xc601, 0xc77c, 0xc774, 0xc0bc, 0xc0ac,
    0xc624, 0xc721, 0xce60, 0xd314, 0xad6c
  },
  { 0xc2ed, 0xbc31, 0xcc9c }, // unit
  { 0xb9cc, 0xc5b5 },         // unit10K
  KOREAN,                     // lang
  false                       // informal
};
static const CJKIdeographicData gDataKoreanHanjaInformal = {
  {                           // digit
    0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db,
    0x4e94, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x5341, 0x767e, 0x5343 }, // unit
  { 0x842c, 0x5104 },         // unit10K
  KOREAN,                     // lang
  true                        // informal
};
static const CJKIdeographicData gDataKoreanHanjaFormal = {
  {                           // digit
    0x96f6, 0x58f9, 0x8cb3, 0x53c3, 0x56db,
    0x4e94, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x62fe, 0x767e, 0x4edf }, // unit
  { 0x842c, 0x5104 },         // unit10K
  KOREAN,                     // lang
  false                       // informal
};
static const CJKIdeographicData gDataSimpChineseInformal = {
  {                           // digit
    0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db,
    0x4e94, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x5341, 0x767e, 0x5343 }, // unit
  { 0x4e07, 0x4ebf },         // unit10K
  CHINESE,                    // lang
  true                        // informal
};
static const CJKIdeographicData gDataSimpChineseFormal = {
  {                           // digit
    0x96f6, 0x58f9, 0x8d30, 0x53c1, 0x8086,
    0x4f0d, 0x9646, 0x67d2, 0x634c, 0x7396
  },
  { 0x62fe, 0x4f70, 0x4edf }, // unit
  { 0x4e07, 0x4ebf },         // unit10K
  CHINESE,                    // lang
  false                       // informal
};
static const CJKIdeographicData gDataTradChineseInformal = {
  {                           // digit
    0x96f6, 0x4e00, 0x4e8c, 0x4e09, 0x56db,
    0x4e94, 0x516d, 0x4e03, 0x516b, 0x4e5d
  },
  { 0x5341, 0x767e, 0x5343 }, // unit
  { 0x842c, 0x5104 },         // unit10K
  CHINESE,                    // lang
  true                        // informal
};
static const CJKIdeographicData gDataTradChineseFormal = {
  {                           // digit
    0x96f6, 0x58f9, 0x8cb3, 0x53c3, 0x8086,
    0x4f0d, 0x9678, 0x67d2, 0x634c, 0x7396
  },
  { 0x62fe, 0x4f70, 0x4edf }, // unit
  { 0x842c, 0x5104 },         // unit10K
  CHINESE,                    // lang
  false                       // informal
};

static bool
CJKIdeographicToText(CounterValue aOrdinal, nsSubstring& 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;
    }
    int32_t cur = 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, nsSubstring& 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, nsSubstring& 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.Insert(NS_LITERAL_STRING("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;
}

class BuiltinCounterStyle : public CounterStyle
{
public:
  friend class CounterStyleManager;

  // will be initialized by CounterStyleManager::InitializeBuiltinCounterStyles
  MOZ_CONSTEXPR BuiltinCounterStyle()
    : CounterStyle(NS_STYLE_LIST_STYLE_NONE)
  {
  }

protected:
  MOZ_CONSTEXPR BuiltinCounterStyle(int32_t aStyle)
    : CounterStyle(aStyle)
  {
  }

public:
  virtual void GetPrefix(nsSubstring& aResult) MOZ_OVERRIDE;
  virtual void GetSuffix(nsSubstring& aResult) MOZ_OVERRIDE;
  virtual void GetSpokenCounterText(CounterValue aOrdinal,
                                    nsSubstring& aResult,
                                    bool& aIsBullet) MOZ_OVERRIDE;
  virtual bool IsBullet() MOZ_OVERRIDE;

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

  virtual void CallFallbackStyle(CounterValue aOrdinal,
                                 nsSubstring& aResult,
                                 bool& aIsRTL) MOZ_OVERRIDE;
  virtual bool GetInitialCounterText(CounterValue aOrdinal,
                                     nsSubstring& aResult,
                                     bool& aIsRTL) MOZ_OVERRIDE;

  // Builtin counter style does not need refcount at all
  NS_IMETHOD_(MozExternalRefCountType) AddRef() MOZ_OVERRIDE { return 2; }
  NS_IMETHOD_(MozExternalRefCountType) Release() MOZ_OVERRIDE { return 2; }
};

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

/* virtual */ void
BuiltinCounterStyle::GetSuffix(nsSubstring& 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:
      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(MOZ_UTF16(", "));
      break;

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

// XXX stolen from nsBlockFrame.cpp
static const char16_t kDiscCharacter = 0x2022;
static const char16_t kCircleCharacter = 0x25e6;
static const char16_t kSquareCharacter = 0x25fe;

/* virtual */ void
BuiltinCounterStyle::GetSpokenCounterText(CounterValue aOrdinal,
                                          nsSubstring& aResult,
                                          bool& aIsBullet)
{
  switch (mStyle) {
    case NS_STYLE_LIST_STYLE_NONE:
      aResult.Truncate();
      aIsBullet = true;
      break;
    case NS_STYLE_LIST_STYLE_DISC:
      aResult.Assign(kDiscCharacter);
      aIsBullet = true;
      break;
    case NS_STYLE_LIST_STYLE_CIRCLE:
      aResult.Assign(kCircleCharacter);
      aIsBullet = true;
      break;
    case NS_STYLE_LIST_STYLE_SQUARE:
      aResult.Assign(kSquareCharacter);
      aIsBullet = true;
      break;
    default:
      CounterStyle::GetSpokenCounterText(aOrdinal, aResult, aIsBullet);
      aIsBullet = false;
      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:
      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(MOZ_UTF16("-"));
  }
  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:
    // 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_MOZ_ETHIOPIC_NUMERIC:
      return aOrdinal >= 1;

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

    // use TamilToText
    case NS_STYLE_LIST_STYLE_MOZ_TAMIL:
      return aOrdinal >= 1 && aOrdinal <= 9999;
  }
}

/* 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:
    // 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_MOZ_ETHIOPIC_NUMERIC:
    case NS_STYLE_LIST_STYLE_MOZ_TAMIL:
      return IsOrdinalInRange(aOrdinal);

    default:
      NS_NOTREACHED("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 */ uint8_t
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:
      return NS_STYLE_COUNTER_SPEAKAS_BULLETS;
    default:
      return NS_STYLE_COUNTER_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:
      return false;
    default:
      return true;
  }
}

/* virtual */ void
BuiltinCounterStyle::CallFallbackStyle(CounterValue aOrdinal,
                                       nsSubstring& aResult,
                                       bool& aIsRTL)
{
  GetFallback()->GetCounterText(aOrdinal, aResult, aIsRTL);
}

/* virtual */ bool
BuiltinCounterStyle::GetInitialCounterText(CounterValue aOrdinal,
                                           nsSubstring& 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_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_MOZ_TAMIL:
      return TamilToText(aOrdinal, aResult);

    case NS_STYLE_LIST_STYLE_MOZ_ETHIOPIC_NUMERIC:
      return EthiopicToText(aOrdinal, aResult);

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

class DependentBuiltinCounterStyle MOZ_FINAL : public BuiltinCounterStyle
{
public:
  DependentBuiltinCounterStyle(int32_t aStyle, CounterStyleManager* aManager)
    : BuiltinCounterStyle(aStyle), 
      mManager(aManager)
  {
    NS_ASSERTION(IsDependentStyle(), "Not a dependent builtin style");
    NS_ABORT_IF_FALSE(!IsCustomStyle(), "Not a builtin style");
  }

  virtual CounterStyle* GetFallback() MOZ_OVERRIDE;

  // DependentBuiltinCounterStyle is managed in the same way as
  // CustomCounterStyle.
  NS_INLINE_DECL_REFCOUNTING(DependentBuiltinCounterStyle)

private:
  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->BuildCounterStyle(NS_LITERAL_STRING("cjk-decimal"));
    default:
      NS_NOTREACHED("Not a valid dependent builtin style");
      return BuiltinCounterStyle::GetFallback();
  }
}

class CustomCounterStyle MOZ_FINAL : public CounterStyle
{
public:
  CustomCounterStyle(CounterStyleManager* aManager,
                     nsCSSCounterStyleRule* aRule)
    : CounterStyle(NS_STYLE_LIST_STYLE_CUSTOM),
      mManager(aManager),
      mRule(aRule),
      mRuleGeneration(aRule->GetGeneration()),
      mSystem(aRule->GetSystem()),
      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();

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

  virtual void GetPrefix(nsSubstring& aResult) MOZ_OVERRIDE;
  virtual void GetSuffix(nsSubstring& aResult) MOZ_OVERRIDE;
  virtual void GetSpokenCounterText(CounterValue aOrdinal,
                                    nsSubstring& aResult,
                                    bool& aIsBullet) MOZ_OVERRIDE;
  virtual bool IsBullet() MOZ_OVERRIDE;

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

  virtual void CallFallbackStyle(CounterValue aOrdinal,
                                 nsSubstring& aResult,
                                 bool& aIsRTL) MOZ_OVERRIDE;
  virtual bool GetInitialCounterText(CounterValue aOrdinal,
                                     nsSubstring& aResult,
                                     bool& aIsRTL) MOZ_OVERRIDE;

  bool IsExtendsSystem()
  {
    return mSystem == NS_STYLE_COUNTER_SYSTEM_EXTENDS;
  }

  // CustomCounterStyle should be reference-counted because it may be
  // dereferenced from the manager but still referenced by nodes and
  // frames before the style change is propagated.
  NS_INLINE_DECL_REFCOUNTING(CustomCounterStyle)

private:
  const nsTArray<nsString>& GetSymbols();
  const nsTArray<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.
  uint8_t GetSpeakAsAutoValue();
  void ComputeRawSpeakAs(uint8_t& 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;

  nsRefPtr<nsCSSCounterStyleRule> mRule;
  uint32_t mRuleGeneration;

  uint8_t mSystem;
  uint8_t 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.
  nsTArray<nsString> mSymbols;
  nsTArray<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 = mRule->GetGeneration();
}

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(nsSubstring& aResult)
{
  if (!(mFlags & FLAG_PREFIX_INITED)) {
    mFlags |= FLAG_PREFIX_INITED;

    const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Prefix);
    if (value.UnitHasStringValue()) {
      value.GetStringValue(mPrefix);
    } else if (IsExtendsSystem()) {
      GetExtends()->GetPrefix(mPrefix);
    } else {
      mPrefix.Truncate();
    }
  }
  aResult = mPrefix;
}

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

    const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Suffix);
    if (value.UnitHasStringValue()) {
      value.GetStringValue(mSuffix);
    } else if (IsExtendsSystem()) {
      GetExtends()->GetSuffix(mSuffix);
    } else {
      mSuffix.AssignLiteral(MOZ_UTF16(". "));
    }
  }
  aResult = mSuffix;
}

/* virtual */ void
CustomCounterStyle::GetSpokenCounterText(CounterValue aOrdinal,
                                         nsSubstring& aResult,
                                         bool& aIsBullet)
{
  if (GetSpeakAs() != NS_STYLE_COUNTER_SPEAKAS_OTHER) {
    CounterStyle::GetSpokenCounterText(aOrdinal, aResult, aIsBullet);
  } else {
    NS_ABORT_IF_FALSE(mSpeakAsCounter,
                      "mSpeakAsCounter should have been initialized.");
    mSpeakAsCounter->GetSpokenCounterText(aOrdinal, aResult, aIsBullet);
  }
}

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

/* virtual */ void
CustomCounterStyle::GetNegative(NegativeType& aResult)
{
  if (!(mFlags & FLAG_NEGATIVE_INITED)) {
    mFlags |= FLAG_NEGATIVE_INITED;
    const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Negative);
    switch (value.GetUnit()) {
      case eCSSUnit_Ident:
      case eCSSUnit_String:
        value.GetStringValue(mNegative.before);
        mNegative.after.Truncate();
        break;
      case eCSSUnit_Pair: {
        const nsCSSValuePair& pair = value.GetPairValue();
        pair.mXValue.GetStringValue(mNegative.before);
        pair.mYValue.GetStringValue(mNegative.after);
        break;
      }
      default: {
        if (IsExtendsSystem()) {
          GetExtends()->GetNegative(mNegative);
        } else {
          mNegative.before.AssignLiteral(MOZ_UTF16("-"));
          mNegative.after.Truncate();
        }
      }
    }
  }
  aResult = mNegative;
}

static inline bool
IsRangeValueInfinite(const nsCSSValue& aValue)
{
  return aValue.GetUnit() == eCSSUnit_Enumerated &&
         aValue.GetIntValue() == NS_STYLE_COUNTER_RANGE_INFINITE;
}

/* virtual */ bool
CustomCounterStyle::IsOrdinalInRange(CounterValue aOrdinal)
{
  const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Range);
  if (value.GetUnit() == eCSSUnit_PairList) {
    for (const nsCSSValuePairList* item = value.GetPairListValue();
         item != nullptr; item = item->mNext) {
      const nsCSSValue& lowerBound = item->mXValue;
      const nsCSSValue& upperBound = item->mYValue;
      if ((IsRangeValueInfinite(lowerBound) ||
           aOrdinal >= lowerBound.GetIntValue()) &&
          (IsRangeValueInfinite(upperBound) ||
           aOrdinal <= upperBound.GetIntValue())) {
        return true;
      }
    }
    return false;
  } else if (IsExtendsSystem() && value.GetUnit() == eCSSUnit_None) {
    // Only use the range of extended style when 'range' is not specified.
    return GetExtends()->IsOrdinalInRange(aOrdinal);
  }
  return IsOrdinalInAutoRange(aOrdinal);
}

/* virtual */ bool
CustomCounterStyle::IsOrdinalInAutoRange(CounterValue aOrdinal)
{
  switch (mSystem) {
    case NS_STYLE_COUNTER_SYSTEM_CYCLIC:
    case NS_STYLE_COUNTER_SYSTEM_NUMERIC:
    case NS_STYLE_COUNTER_SYSTEM_FIXED:
      return true;
    case NS_STYLE_COUNTER_SYSTEM_ALPHABETIC:
    case NS_STYLE_COUNTER_SYSTEM_SYMBOLIC:
      return aOrdinal >= 1;
    case NS_STYLE_COUNTER_SYSTEM_ADDITIVE:
      return aOrdinal >= 0;
    case NS_STYLE_COUNTER_SYSTEM_EXTENDS:
      return GetExtendsRoot()->IsOrdinalInAutoRange(aOrdinal);
    default:
      NS_NOTREACHED("Invalid system for computing auto value.");
      return false;
  }
}

/* virtual */ void
CustomCounterStyle::GetPad(PadType& aResult)
{
  if (!(mFlags & FLAG_PAD_INITED)) {
    mFlags |= FLAG_PAD_INITED;
    const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Pad);
    if (value.GetUnit() == eCSSUnit_Pair) {
      const nsCSSValuePair& pair = value.GetPairValue();
      mPad.width = pair.mXValue.GetIntValue();
      pair.mYValue.GetStringValue(mPad.symbol);
    } else if (IsExtendsSystem()) {
      GetExtends()->GetPad(mPad);
    } else {
      mPad.width = 0;
      mPad.symbol.Truncate();
    }
  }
  aResult = mPad;
}

/* virtual */ CounterStyle*
CustomCounterStyle::GetFallback()
{
  if (!mFallback) {
    const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_Fallback);
    if (value.UnitHasStringValue()) {
      mFallback = mManager->BuildCounterStyle(
          nsDependentString(value.GetStringBufferValue()));
    } else if (IsExtendsSystem()) {
      mFallback = GetExtends()->GetFallback();
    } else {
      mFallback = CounterStyleManager::GetDecimalStyle();
    }
  }
  return mFallback;
}

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

/* virtual */ bool
CustomCounterStyle::UseNegativeSign()
{
  switch (mSystem) {
    case NS_STYLE_COUNTER_SYSTEM_SYMBOLIC:
    case NS_STYLE_COUNTER_SYSTEM_ALPHABETIC:
    case NS_STYLE_COUNTER_SYSTEM_NUMERIC:
    case NS_STYLE_COUNTER_SYSTEM_ADDITIVE:
      return true;
    case NS_STYLE_COUNTER_SYSTEM_EXTENDS:
      return GetExtendsRoot()->UseNegativeSign();
    default:
      return false;
  }
}

/* virtual */ void
CustomCounterStyle::CallFallbackStyle(CounterValue aOrdinal,
                                      nsSubstring& 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, aResult, aIsRTL);
  mFallback = fallback;
}

/* virtual */ bool
CustomCounterStyle::GetInitialCounterText(CounterValue aOrdinal,
                                          nsSubstring& aResult,
                                          bool& aIsRTL)
{
  switch (mSystem) {
    case NS_STYLE_COUNTER_SYSTEM_CYCLIC:
      return GetCyclicCounterText(aOrdinal, aResult, GetSymbols());
    case NS_STYLE_COUNTER_SYSTEM_FIXED: {
      int32_t start = mRule->GetSystemArgument().GetIntValue();
      return GetFixedCounterText(aOrdinal, aResult, start, GetSymbols());
    }
    case NS_STYLE_COUNTER_SYSTEM_SYMBOLIC:
      return GetSymbolicCounterText(aOrdinal, aResult, GetSymbols());
    case NS_STYLE_COUNTER_SYSTEM_ALPHABETIC:
      return GetAlphabeticCounterText(aOrdinal, aResult, GetSymbols());
    case NS_STYLE_COUNTER_SYSTEM_NUMERIC:
      return GetNumericCounterText(aOrdinal, aResult, GetSymbols());
    case NS_STYLE_COUNTER_SYSTEM_ADDITIVE:
      return GetAdditiveCounterText(aOrdinal, aResult, GetAdditiveSymbols());
    case NS_STYLE_COUNTER_SYSTEM_EXTENDS:
      return GetExtendsRoot()->
        GetInitialCounterText(aOrdinal, aResult, aIsRTL);
    default:
      NS_NOTREACHED("Invalid system.");
      return false;
  }
}

const nsTArray<nsString>&
CustomCounterStyle::GetSymbols()
{
  if (mSymbols.IsEmpty()) {
    const nsCSSValue& values = mRule->GetDesc(eCSSCounterDesc_Symbols);
    for (const nsCSSValueList* item = values.GetListValue();
         item; item = item->mNext) {
      nsString* symbol = mSymbols.AppendElement();
      item->mValue.GetStringValue(*symbol);
    }
    mSymbols.Compact();
  }
  return mSymbols;
}

const nsTArray<AdditiveSymbol>&
CustomCounterStyle::GetAdditiveSymbols()
{
  if (mAdditiveSymbols.IsEmpty()) {
    const nsCSSValue& values = mRule->GetDesc(eCSSCounterDesc_AdditiveSymbols);
    for (const nsCSSValuePairList* item = values.GetPairListValue();
         item; item = item->mNext) {
      AdditiveSymbol* symbol = mAdditiveSymbols.AppendElement();
      symbol->weight = item->mXValue.GetIntValue();
      item->mYValue.GetStringValue(symbol->symbol);
    }
    mAdditiveSymbols.Compact();
  }
  return mAdditiveSymbols;
}

// This method is used to provide the computed value for 'auto'.
uint8_t
CustomCounterStyle::GetSpeakAsAutoValue()
{
  uint8_t 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;
  }
  switch (system) {
    case NS_STYLE_COUNTER_SYSTEM_ALPHABETIC:
      return NS_STYLE_COUNTER_SPEAKAS_SPELL_OUT;
    case NS_STYLE_COUNTER_SYSTEM_CYCLIC:
      return NS_STYLE_COUNTER_SPEAKAS_BULLETS;
    default:
      return NS_STYLE_COUNTER_SPEAKAS_NUMBERS;
  }
}

// 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(uint8_t& aSpeakAs,
                                    CounterStyle*& aSpeakAsCounter)
{
  NS_ASSERTION(!(mFlags & FLAG_SPEAKAS_INITED),
               "ComputeRawSpeakAs is called with speak-as inited.");

  const nsCSSValue& value = mRule->GetDesc(eCSSCounterDesc_SpeakAs);
  switch (value.GetUnit()) {
    case eCSSUnit_Auto:
      aSpeakAs = GetSpeakAsAutoValue();
      break;
    case eCSSUnit_Enumerated:
      aSpeakAs = value.GetIntValue();
      break;
    case eCSSUnit_Ident:
      aSpeakAs = NS_STYLE_COUNTER_SPEAKAS_OTHER;
      aSpeakAsCounter = mManager->BuildCounterStyle(
          nsDependentString(value.GetStringBufferValue()));
      break;
    case eCSSUnit_Null: {
      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:
      NS_NOTREACHED("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 == NS_STYLE_COUNTER_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 != NS_STYLE_COUNTER_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;
  }

  const nsCSSValue& value = mRule->GetSystemArgument();
  CounterStyle* nextCounter = mManager->BuildCounterStyle(
      nsDependentString(value.GetStringBufferValue()));
  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;
}

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;
  }
}

static int32_t
CountGraphemeClusters(const nsSubstring& aText)
{
  using mozilla::unicode::ClusterIterator;
  ClusterIterator iter(aText.Data(), aText.Length());
  int32_t result = 0;
  while (!iter.AtEnd()) {
    ++result;
    iter.Next();
  }
  return result;
}

void
CounterStyle::GetCounterText(CounterValue aOrdinal,
                             nsSubstring& 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, 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 - CountGraphemeClusters(initialText);
      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, aResult, aIsRTL);
  }
}

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

static BuiltinCounterStyle gBuiltinStyleTable[NS_STYLE_LIST_STYLE__MAX];

CounterStyleManager::CounterStyleManager(nsPresContext* aPresContext)
  : mPresContext(aPresContext)
{
  // Insert the static styles into cache table
  mCacheTable.Put(NS_LITERAL_STRING("none"), GetNoneStyle());
  mCacheTable.Put(NS_LITERAL_STRING("decimal"), GetDecimalStyle());
}

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

/* static */ void
CounterStyleManager::InitializeBuiltinCounterStyles()
{
  for (uint32_t i = 0; i < NS_STYLE_LIST_STYLE__MAX; ++i) {
    gBuiltinStyleTable[i].mStyle = i;
  }
}

#ifdef DEBUG
static PLDHashOperator
CheckRefCount(const nsSubstring& aKey,
              CounterStyle* aStyle,
              void* aArg)
{
  aStyle->AddRef();
  auto refcnt = aStyle->Release();
  NS_ASSERTION(!aStyle->IsDependentStyle() || refcnt == 1,
               "Counter style is still referenced by other objects.");
  return PL_DHASH_NEXT;
}
#endif

void
CounterStyleManager::Disconnect()
{
#ifdef DEBUG
  mCacheTable.EnumerateRead(CheckRefCount, nullptr);
#endif
  mCacheTable.Clear();
  mPresContext = nullptr;
}

CounterStyle*
CounterStyleManager::BuildCounterStyle(const nsSubstring& aName)
{
  CounterStyle* data = mCacheTable.GetWeak(aName);
  if (data) {
    return data;
  }

  // It is intentional that the predefined names are case-insensitive
  // but the user-defined names case-sensitive.
  nsCSSCounterStyleRule* rule =
    mPresContext->StyleSet()->CounterStyleRuleForName(mPresContext, aName);
  if (rule) {
    data = new CustomCounterStyle(this, rule);
  } else {
    int32_t type;
    nsCSSKeyword keyword = nsCSSKeywords::LookupKeyword(aName);
    if (nsCSSProps::FindKeyword(keyword, nsCSSProps::kListStyleKTable, type)) {
      if (gBuiltinStyleTable[type].IsDependentStyle()) {
        data = new DependentBuiltinCounterStyle(type, this);
      } else {
        data = GetBuiltinStyle(type);
      }
    }
  }
  if (!data) {
    data = GetDecimalStyle();
  }
  mCacheTable.Put(aName, data);
  return data;
}

/* static */ CounterStyle*
CounterStyleManager::GetBuiltinStyle(int32_t aStyle)
{
  NS_ABORT_IF_FALSE(0 <= aStyle && aStyle < NS_STYLE_LIST_STYLE__MAX,
                    "Require a valid builtin style constant");
  NS_ABORT_IF_FALSE(!gBuiltinStyleTable[aStyle].IsDependentStyle(),
                    "Cannot get dependent builtin style");
  NS_ASSERTION(aStyle != NS_STYLE_LIST_STYLE_LOWER_ROMAN &&
               aStyle != NS_STYLE_LIST_STYLE_UPPER_ROMAN &&
               aStyle != NS_STYLE_LIST_STYLE_LOWER_ALPHA &&
               aStyle != NS_STYLE_LIST_STYLE_UPPER_ALPHA,
               "lower/upper-roman/alpha should be custom counter style");
  return &gBuiltinStyleTable[aStyle];
}

struct InvalidateOldStyleData
{
  explicit InvalidateOldStyleData(nsPresContext* aPresContext)
    : mPresContext(aPresContext),
      mChanged(false)
  {
  }

  nsPresContext* mPresContext;
  nsTArray<nsRefPtr<CounterStyle>> mToBeRemoved;
  bool mChanged;
};

static PLDHashOperator
InvalidateOldStyle(const nsSubstring& aKey,
                   nsRefPtr<CounterStyle>& aStyle,
                   void* aArg)
{
  InvalidateOldStyleData* data = static_cast<InvalidateOldStyleData*>(aArg);
  bool toBeUpdated = false;
  bool toBeRemoved = false;
  nsCSSCounterStyleRule* newRule = data->mPresContext->
    StyleSet()->CounterStyleRuleForName(data->mPresContext, aKey);
  if (!newRule) {
    if (aStyle->IsCustomStyle()) {
      toBeRemoved = true;
    }
  } else {
    if (!aStyle->IsCustomStyle()) {
      toBeRemoved = true;
    } else {
      CustomCounterStyle* style =
        static_cast<CustomCounterStyle*>(aStyle.get());
      if (style->GetRule() != newRule) {
        toBeRemoved = true;
      } else if (style->GetRuleGeneration() != newRule->GetGeneration()) {
        toBeUpdated = true;
        style->ResetCachedData();
      }
    }
  }
  data->mChanged = data->mChanged || toBeUpdated || toBeRemoved;
  if (toBeRemoved) {
    if (aStyle->IsDependentStyle()) {
      // The object has to be held here so that it will not be released
      // before all pointers that refer to it are reset. It will be
      // released when the MarkAndCleanData goes out of scope at the end
      // of NotifyRuleChanged().
      data->mToBeRemoved.AppendElement(aStyle);
    }
    return PL_DHASH_REMOVE;
  }
  return PL_DHASH_NEXT;
}

static PLDHashOperator
InvalidateDependentData(const nsSubstring& aKey,
                        CounterStyle* aStyle,
                        void* aArg)
{
  if (aStyle->IsCustomStyle()) {
    CustomCounterStyle* custom = static_cast<CustomCounterStyle*>(aStyle);
    custom->ResetDependentData();
  }
  // There is no dependent data cached in DependentBuiltinCounterStyle
  // instances, so we don't need to reset their data.
  return PL_DHASH_NEXT;
}

bool
CounterStyleManager::NotifyRuleChanged()
{
  InvalidateOldStyleData data(mPresContext);
  mCacheTable.Enumerate(InvalidateOldStyle, &data);
  if (data.mChanged) {
    mCacheTable.EnumerateRead(InvalidateDependentData, nullptr);
  }
  return data.mChanged;
}

} // namespace mozilla