/*
 * Copyright (c) 2021-2025, Tim Flynn <trflynn89@ladybird.org>
 *
 * SPDX-License-Identifier: BSD-2-Clause
 */

#include <AK/CharacterTypes.h>
#include <AK/QuickSort.h>
#include <LibUnicode/ICU.h>
#include <LibUnicode/Locale.h>
#include <LibUnicode/NumberFormat.h>
#include <LibUnicode/PartitionRange.h>
#include <math.h>

#include <unicode/numberformatter.h>
#include <unicode/numberrangeformatter.h>
#include <unicode/plurrule.h>

namespace Unicode {

NumberFormatStyle number_format_style_from_string(StringView number_format_style)
{
    if (number_format_style == "decimal"sv)
        return NumberFormatStyle::Decimal;
    if (number_format_style == "percent"sv)
        return NumberFormatStyle::Percent;
    if (number_format_style == "currency"sv)
        return NumberFormatStyle::Currency;
    if (number_format_style == "unit"sv)
        return NumberFormatStyle::Unit;
    VERIFY_NOT_REACHED();
}

NumberFormatStyle number_format_style_from_string(Utf16View number_format_style)
{
    if (number_format_style == "decimal"sv)
        return NumberFormatStyle::Decimal;
    if (number_format_style == "percent"sv)
        return NumberFormatStyle::Percent;
    if (number_format_style == "currency"sv)
        return NumberFormatStyle::Currency;
    if (number_format_style == "unit"sv)
        return NumberFormatStyle::Unit;
    VERIFY_NOT_REACHED();
}

Utf16String number_format_style_to_string(NumberFormatStyle number_format_style)
{
    switch (number_format_style) {
    case NumberFormatStyle::Decimal:
        return "decimal"_utf16;
    case NumberFormatStyle::Percent:
        return "percent"_utf16;
    case NumberFormatStyle::Currency:
        return "currency"_utf16;
    case NumberFormatStyle::Unit:
        return "unit"_utf16;
    }
    VERIFY_NOT_REACHED();
}

SignDisplay sign_display_from_string(StringView sign_display)
{
    if (sign_display == "auto"sv)
        return SignDisplay::Auto;
    if (sign_display == "never"sv)
        return SignDisplay::Never;
    if (sign_display == "always"sv)
        return SignDisplay::Always;
    if (sign_display == "exceptZero"sv)
        return SignDisplay::ExceptZero;
    if (sign_display == "negative"sv)
        return SignDisplay::Negative;
    VERIFY_NOT_REACHED();
}

SignDisplay sign_display_from_string(Utf16View sign_display)
{
    if (sign_display == "auto"sv)
        return SignDisplay::Auto;
    if (sign_display == "never"sv)
        return SignDisplay::Never;
    if (sign_display == "always"sv)
        return SignDisplay::Always;
    if (sign_display == "exceptZero"sv)
        return SignDisplay::ExceptZero;
    if (sign_display == "negative"sv)
        return SignDisplay::Negative;
    VERIFY_NOT_REACHED();
}

Utf16String sign_display_to_string(SignDisplay sign_display)
{
    switch (sign_display) {
    case SignDisplay::Auto:
        return "auto"_utf16;
    case SignDisplay::Never:
        return "never"_utf16;
    case SignDisplay::Always:
        return "always"_utf16;
    case SignDisplay::ExceptZero:
        return "exceptZero"_utf16;
    case SignDisplay::Negative:
        return "negative"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberSignDisplay icu_sign_display(SignDisplay sign_display, Optional<CurrencySign> const& currency_sign)
{
    switch (sign_display) {
    case SignDisplay::Auto:
        return currency_sign == CurrencySign::Standard ? UNUM_SIGN_AUTO : UNUM_SIGN_ACCOUNTING;
    case SignDisplay::Never:
        return UNUM_SIGN_NEVER;
    case SignDisplay::Always:
        return currency_sign == CurrencySign::Standard ? UNUM_SIGN_ALWAYS : UNUM_SIGN_ACCOUNTING_ALWAYS;
    case SignDisplay::ExceptZero:
        return currency_sign == CurrencySign::Standard ? UNUM_SIGN_EXCEPT_ZERO : UNUM_SIGN_ACCOUNTING_EXCEPT_ZERO;
    case SignDisplay::Negative:
        return currency_sign == CurrencySign::Standard ? UNUM_SIGN_NEGATIVE : UNUM_SIGN_ACCOUNTING_NEGATIVE;
    }
    VERIFY_NOT_REACHED();
}

Notation notation_from_string(StringView notation)
{
    if (notation == "standard"sv)
        return Notation::Standard;
    if (notation == "scientific"sv)
        return Notation::Scientific;
    if (notation == "engineering"sv)
        return Notation::Engineering;
    if (notation == "compact"sv)
        return Notation::Compact;
    VERIFY_NOT_REACHED();
}

Notation notation_from_string(Utf16View notation)
{
    if (notation == "standard"sv)
        return Notation::Standard;
    if (notation == "scientific"sv)
        return Notation::Scientific;
    if (notation == "engineering"sv)
        return Notation::Engineering;
    if (notation == "compact"sv)
        return Notation::Compact;
    VERIFY_NOT_REACHED();
}

Utf16String notation_to_string(Notation notation)
{
    switch (notation) {
    case Notation::Standard:
        return "standard"_utf16;
    case Notation::Scientific:
        return "scientific"_utf16;
    case Notation::Engineering:
        return "engineering"_utf16;
    case Notation::Compact:
        return "compact"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static icu::number::Notation icu_notation(Notation notation, Optional<CompactDisplay> const& compact_display)
{
    switch (notation) {
    case Notation::Standard:
        return icu::number::Notation::simple();
    case Notation::Scientific:
        return icu::number::Notation::scientific();
    case Notation::Engineering:
        return icu::number::Notation::engineering();
    case Notation::Compact:
        switch (*compact_display) {
        case CompactDisplay::Short:
            return icu::number::Notation::compactShort();
        case CompactDisplay::Long:
            return icu::number::Notation::compactLong();
        }
    }
    VERIFY_NOT_REACHED();
}

CompactDisplay compact_display_from_string(StringView compact_display)
{
    if (compact_display == "short"sv)
        return CompactDisplay::Short;
    if (compact_display == "long"sv)
        return CompactDisplay::Long;
    VERIFY_NOT_REACHED();
}

CompactDisplay compact_display_from_string(Utf16View compact_display)
{
    if (compact_display == "short"sv)
        return CompactDisplay::Short;
    if (compact_display == "long"sv)
        return CompactDisplay::Long;
    VERIFY_NOT_REACHED();
}

Utf16String compact_display_to_string(CompactDisplay compact_display)
{
    switch (compact_display) {
    case CompactDisplay::Short:
        return "short"_utf16;
    case CompactDisplay::Long:
        return "long"_utf16;
    }
    VERIFY_NOT_REACHED();
}

Grouping grouping_from_string(StringView grouping)
{
    if (grouping == "always"sv)
        return Grouping::Always;
    if (grouping == "auto"sv)
        return Grouping::Auto;
    if (grouping == "min2"sv)
        return Grouping::Min2;
    if (grouping == "false"sv)
        return Grouping::False;
    VERIFY_NOT_REACHED();
}

Utf16String grouping_to_string(Grouping grouping)
{
    switch (grouping) {
    case Grouping::Always:
        return "always"_utf16;
    case Grouping::Auto:
        return "auto"_utf16;
    case Grouping::Min2:
        return "min2"_utf16;
    case Grouping::False:
        return "false"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberGroupingStrategy icu_grouping_strategy(Grouping grouping)
{
    switch (grouping) {
    case Grouping::Always:
        return UNUM_GROUPING_ON_ALIGNED;
    case Grouping::Auto:
        return UNUM_GROUPING_AUTO;
    case Grouping::Min2:
        return UNUM_GROUPING_MIN2;
    case Grouping::False:
        return UNUM_GROUPING_OFF;
    }
    VERIFY_NOT_REACHED();
}

CurrencyDisplay currency_display_from_string(StringView currency_display)
{
    if (currency_display == "code"sv)
        return CurrencyDisplay::Code;
    if (currency_display == "symbol"sv)
        return CurrencyDisplay::Symbol;
    if (currency_display == "narrowSymbol"sv)
        return CurrencyDisplay::NarrowSymbol;
    if (currency_display == "name"sv)
        return CurrencyDisplay::Name;
    VERIFY_NOT_REACHED();
}

CurrencyDisplay currency_display_from_string(Utf16View currency_display)
{
    if (currency_display == "code"sv)
        return CurrencyDisplay::Code;
    if (currency_display == "symbol"sv)
        return CurrencyDisplay::Symbol;
    if (currency_display == "narrowSymbol"sv)
        return CurrencyDisplay::NarrowSymbol;
    if (currency_display == "name"sv)
        return CurrencyDisplay::Name;
    VERIFY_NOT_REACHED();
}

Utf16String currency_display_to_string(CurrencyDisplay currency_display)
{
    switch (currency_display) {
    case CurrencyDisplay::Code:
        return "code"_utf16;
    case CurrencyDisplay::Symbol:
        return "symbol"_utf16;
    case CurrencyDisplay::NarrowSymbol:
        return "narrowSymbol"_utf16;
    case CurrencyDisplay::Name:
        return "name"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberUnitWidth icu_currency_display(CurrencyDisplay currency_display)
{
    switch (currency_display) {
    case CurrencyDisplay::Code:
        return UNUM_UNIT_WIDTH_ISO_CODE;
    case CurrencyDisplay::Symbol:
        return UNUM_UNIT_WIDTH_SHORT;
    case CurrencyDisplay::NarrowSymbol:
        return UNUM_UNIT_WIDTH_NARROW;
    case CurrencyDisplay::Name:
        return UNUM_UNIT_WIDTH_FULL_NAME;
    }
    VERIFY_NOT_REACHED();
}

CurrencySign currency_sign_from_string(StringView currency_sign)
{
    if (currency_sign == "standard"sv)
        return CurrencySign::Standard;
    if (currency_sign == "accounting"sv)
        return CurrencySign::Accounting;
    VERIFY_NOT_REACHED();
}

CurrencySign currency_sign_from_string(Utf16View currency_sign)
{
    if (currency_sign == "standard"sv)
        return CurrencySign::Standard;
    if (currency_sign == "accounting"sv)
        return CurrencySign::Accounting;
    VERIFY_NOT_REACHED();
}

Utf16String currency_sign_to_string(CurrencySign currency_sign)
{
    switch (currency_sign) {
    case CurrencySign::Standard:
        return "standard"_utf16;
    case CurrencySign::Accounting:
        return "accounting"_utf16;
    }
    VERIFY_NOT_REACHED();
}

RoundingType rounding_type_from_string(StringView rounding_type)
{
    if (rounding_type == "significantDigits"sv)
        return RoundingType::SignificantDigits;
    if (rounding_type == "fractionDigits"sv)
        return RoundingType::FractionDigits;
    if (rounding_type == "morePrecision"sv)
        return RoundingType::MorePrecision;
    if (rounding_type == "lessPrecision"sv)
        return RoundingType::LessPrecision;
    VERIFY_NOT_REACHED();
}

Utf16String rounding_type_to_string(RoundingType rounding_type)
{
    switch (rounding_type) {
    case RoundingType::SignificantDigits:
        return "significantDigits"_utf16;
    case RoundingType::FractionDigits:
        return "fractionDigits"_utf16;
    case RoundingType::MorePrecision:
        return "morePrecision"_utf16;
    case RoundingType::LessPrecision:
        return "lessPrecision"_utf16;
    }
    VERIFY_NOT_REACHED();
}

RoundingMode rounding_mode_from_string(StringView rounding_mode)
{
    if (rounding_mode == "ceil"sv)
        return RoundingMode::Ceil;
    if (rounding_mode == "expand"sv)
        return RoundingMode::Expand;
    if (rounding_mode == "floor"sv)
        return RoundingMode::Floor;
    if (rounding_mode == "halfCeil"sv)
        return RoundingMode::HalfCeil;
    if (rounding_mode == "halfEven"sv)
        return RoundingMode::HalfEven;
    if (rounding_mode == "halfExpand"sv)
        return RoundingMode::HalfExpand;
    if (rounding_mode == "halfFloor"sv)
        return RoundingMode::HalfFloor;
    if (rounding_mode == "halfTrunc"sv)
        return RoundingMode::HalfTrunc;
    if (rounding_mode == "trunc"sv)
        return RoundingMode::Trunc;
    VERIFY_NOT_REACHED();
}

RoundingMode rounding_mode_from_string(Utf16View rounding_mode)
{
    if (rounding_mode == "ceil"sv)
        return RoundingMode::Ceil;
    if (rounding_mode == "expand"sv)
        return RoundingMode::Expand;
    if (rounding_mode == "floor"sv)
        return RoundingMode::Floor;
    if (rounding_mode == "halfCeil"sv)
        return RoundingMode::HalfCeil;
    if (rounding_mode == "halfEven"sv)
        return RoundingMode::HalfEven;
    if (rounding_mode == "halfExpand"sv)
        return RoundingMode::HalfExpand;
    if (rounding_mode == "halfFloor"sv)
        return RoundingMode::HalfFloor;
    if (rounding_mode == "halfTrunc"sv)
        return RoundingMode::HalfTrunc;
    if (rounding_mode == "trunc"sv)
        return RoundingMode::Trunc;
    VERIFY_NOT_REACHED();
}

Utf16String rounding_mode_to_string(RoundingMode rounding_mode)
{
    switch (rounding_mode) {
    case RoundingMode::Ceil:
        return "ceil"_utf16;
    case RoundingMode::Expand:
        return "expand"_utf16;
    case RoundingMode::Floor:
        return "floor"_utf16;
    case RoundingMode::HalfCeil:
        return "halfCeil"_utf16;
    case RoundingMode::HalfEven:
        return "halfEven"_utf16;
    case RoundingMode::HalfExpand:
        return "halfExpand"_utf16;
    case RoundingMode::HalfFloor:
        return "halfFloor"_utf16;
    case RoundingMode::HalfTrunc:
        return "halfTrunc"_utf16;
    case RoundingMode::Trunc:
        return "trunc"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberFormatRoundingMode icu_rounding_mode(RoundingMode rounding_mode)
{
    switch (rounding_mode) {
    case RoundingMode::Ceil:
        return UNUM_ROUND_CEILING;
    case RoundingMode::Expand:
        return UNUM_ROUND_UP;
    case RoundingMode::Floor:
        return UNUM_ROUND_FLOOR;
    case RoundingMode::HalfCeil:
        return UNUM_ROUND_HALF_CEILING;
    case RoundingMode::HalfEven:
        return UNUM_ROUND_HALFEVEN;
    case RoundingMode::HalfExpand:
        return UNUM_ROUND_HALFUP;
    case RoundingMode::HalfFloor:
        return UNUM_ROUND_HALF_FLOOR;
    case RoundingMode::HalfTrunc:
        return UNUM_ROUND_HALFDOWN;
    case RoundingMode::Trunc:
        return UNUM_ROUND_DOWN;
    }
    VERIFY_NOT_REACHED();
}

TrailingZeroDisplay trailing_zero_display_from_string(StringView trailing_zero_display)
{
    if (trailing_zero_display == "auto"sv)
        return TrailingZeroDisplay::Auto;
    if (trailing_zero_display == "stripIfInteger"sv)
        return TrailingZeroDisplay::StripIfInteger;
    VERIFY_NOT_REACHED();
}

TrailingZeroDisplay trailing_zero_display_from_string(Utf16View trailing_zero_display)
{
    if (trailing_zero_display == "auto"sv)
        return TrailingZeroDisplay::Auto;
    if (trailing_zero_display == "stripIfInteger"sv)
        return TrailingZeroDisplay::StripIfInteger;
    VERIFY_NOT_REACHED();
}

Utf16String trailing_zero_display_to_string(TrailingZeroDisplay trailing_zero_display)
{
    switch (trailing_zero_display) {
    case TrailingZeroDisplay::Auto:
        return "auto"_utf16;
    case TrailingZeroDisplay::StripIfInteger:
        return "stripIfInteger"_utf16;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberTrailingZeroDisplay icu_trailing_zero_display(TrailingZeroDisplay trailing_zero_display)
{
    switch (trailing_zero_display) {
    case TrailingZeroDisplay::Auto:
        return UNUM_TRAILING_ZERO_AUTO;
    case TrailingZeroDisplay::StripIfInteger:
        return UNUM_TRAILING_ZERO_HIDE_IF_WHOLE;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UNumberUnitWidth icu_unit_width(Style unit_display)
{
    switch (unit_display) {
    case Style::Long:
        return UNUM_UNIT_WIDTH_FULL_NAME;
    case Style::Short:
        return UNUM_UNIT_WIDTH_SHORT;
    case Style::Narrow:
        return UNUM_UNIT_WIDTH_NARROW;
    }
    VERIFY_NOT_REACHED();
}

static constexpr UPluralType icu_plural_type(PluralForm plural_form)
{
    switch (plural_form) {
    case PluralForm::Cardinal:
        return UPluralType::UPLURAL_TYPE_CARDINAL;
    case PluralForm::Ordinal:
        return UPluralType::UPLURAL_TYPE_ORDINAL;
    }
    VERIFY_NOT_REACHED();
}

static void apply_display_options(icu::number::LocalizedNumberFormatter& formatter, DisplayOptions const& display_options)
{
    UErrorCode status = U_ZERO_ERROR;

    switch (display_options.style) {
    case NumberFormatStyle::Decimal:
        break;

    case NumberFormatStyle::Percent:
        formatter = formatter.unit(icu::MeasureUnit::getPercent()).scale(icu::number::Scale::byDouble(100));
        break;

    case NumberFormatStyle::Currency: {
        VERIFY(display_options.currency->length_in_code_units() == 3);
        UChar currency_code[4] {
            display_options.currency->code_unit_at(0),
            display_options.currency->code_unit_at(1),
            display_options.currency->code_unit_at(2),
            0,
        };
        formatter = formatter.unit(icu::CurrencyUnit(currency_code, status));
        formatter = formatter.unitWidth(icu_currency_display(*display_options.currency_display));
        verify_icu_success(status);
        break;
    }

    case NumberFormatStyle::Unit:
        auto unit = display_options.unit->to_utf8();
        formatter = formatter.unit(icu::MeasureUnit::forIdentifier(icu_string_piece(unit.bytes_as_string_view()), status));
        formatter = formatter.unitWidth(icu_unit_width(*display_options.unit_display));
        verify_icu_success(status);
        break;
    }

    formatter = formatter.sign(icu_sign_display(display_options.sign_display, display_options.currency_sign));
    formatter = formatter.notation(icu_notation(display_options.notation, display_options.compact_display));
    formatter = formatter.grouping(icu_grouping_strategy(display_options.grouping));
}

static void apply_rounding_options(icu::number::LocalizedNumberFormatter& formatter, RoundingOptions const& rounding_options)
{
    auto precision = icu::number::Precision::unlimited();

    if (rounding_options.rounding_increment == 1) {
        switch (rounding_options.type) {
        case RoundingType::SignificantDigits:
            precision = icu::number::Precision::minMaxSignificantDigits(*rounding_options.min_significant_digits, *rounding_options.max_significant_digits);
            break;
        case RoundingType::FractionDigits:
            precision = icu::number::Precision::minMaxFraction(*rounding_options.min_fraction_digits, *rounding_options.max_fraction_digits);
            break;
        case RoundingType::MorePrecision:
            precision = icu::number::Precision::minMaxFraction(*rounding_options.min_fraction_digits, *rounding_options.max_fraction_digits)
                            .withSignificantDigits(*rounding_options.min_significant_digits, *rounding_options.max_significant_digits, UNUM_ROUNDING_PRIORITY_RELAXED);
            break;
        case RoundingType::LessPrecision:
            precision = icu::number::Precision::minMaxFraction(*rounding_options.min_fraction_digits, *rounding_options.max_fraction_digits)
                            .withSignificantDigits(*rounding_options.min_significant_digits, *rounding_options.max_significant_digits, UNUM_ROUNDING_PRIORITY_STRICT);
            break;
        }
    } else {
        auto mantissa = rounding_options.rounding_increment;
        auto magnitude = *rounding_options.max_fraction_digits * -1;

        precision = icu::number::Precision::incrementExact(mantissa, static_cast<i16>(magnitude))
                        .withMinFraction(*rounding_options.min_fraction_digits);
    }

    formatter = formatter.precision(precision.trailingZeroDisplay(icu_trailing_zero_display(rounding_options.trailing_zero_display)));
    formatter = formatter.integerWidth(icu::number::IntegerWidth::zeroFillTo(rounding_options.min_integer_digits));
    formatter = formatter.roundingMode(icu_rounding_mode(rounding_options.mode));
}

static Utf16String icu_number_format_field_to_string(i32 field, NumberFormat::Value const& value, bool is_unit)
{
    switch (field) {
    case PartitionRange::LITERAL_FIELD:
        return "literal"_utf16;
    case UNUM_INTEGER_FIELD:
        if (auto const* number = value.get_pointer<double>()) {
            if (isnan(*number))
                return "nan"_utf16;
            if (isinf(*number))
                return "infinity"_utf16;
        }
        return "integer"_utf16;
    case UNUM_FRACTION_FIELD:
        return "fraction"_utf16;
    case UNUM_DECIMAL_SEPARATOR_FIELD:
        return "decimal"_utf16;
    case UNUM_EXPONENT_SYMBOL_FIELD:
        return "exponentSeparator"_utf16;
    case UNUM_EXPONENT_SIGN_FIELD:
        return "exponentMinusSign"_utf16;
    case UNUM_EXPONENT_FIELD:
        return "exponentInteger"_utf16;
    case UNUM_GROUPING_SEPARATOR_FIELD:
        return "group"_utf16;
    case UNUM_CURRENCY_FIELD:
        return "currency"_utf16;
    case UNUM_PERCENT_FIELD:
        return is_unit ? "unit"_utf16 : "percentSign"_utf16;
    case UNUM_SIGN_FIELD: {
        auto is_negative = value.visit(
            [&](double number) { return signbit(number); },
            [&](Utf16String const& number) { return number.starts_with('-'); });
        return is_negative ? "minusSign"_utf16 : "plusSign"_utf16;
    }
    case UNUM_MEASURE_UNIT_FIELD:
        return "unit"_utf16;
    case UNUM_COMPACT_FIELD:
        return "compact"_utf16;
    case UNUM_APPROXIMATELY_SIGN_FIELD:
        return "approximatelySign"_utf16;
    }

    VERIFY_NOT_REACHED();
}

// ICU will give us overlapping partitions, e.g. for the formatted result "1,234", we will get the following parts:
//
//     part=","     type=group    start=1  end=2
//     part="1,234" type=integer  start=0  end=5
//
// We need to massage these partitions into non-overlapping parts for ECMA-402:
//
//     part="1"     type=integer  start=0  end=1
//     part=","     type=group    start=1  end=2
//     part="234"   type=integer  start=2  end=5
static void flatten_partitions(Vector<PartitionRange>& partitions)
{
    if (partitions.size() <= 1)
        return;

    quick_sort(partitions);

    auto subtract_range = [&](auto const& first, auto const& second) -> Vector<PartitionRange> {
        if (second.start > first.end || first.start > second.end)
            return { first };

        Vector<PartitionRange> result;

        if (second.start > first.start)
            result.empend(first.field, first.start, second.start);
        if (second.end < first.end)
            result.empend(first.field, second.end, first.end);

        return result;
    };

    for (size_t i = 0; i < partitions.size(); ++i) {
        for (size_t j = i + 1; j < partitions.size(); ++j) {
            auto& first = partitions[i];
            auto& second = partitions[j];

            auto result = subtract_range(first, second);

            if (result.is_empty()) {
                partitions.remove(i);
                --i;
                break;
            }

            first = result[0];

            if (result.size() == 2)
                partitions.insert(i + 1, result[1]);
        }
    }

    quick_sort(partitions);
}

class NumberFormatImpl : public NumberFormat {
public:
    NumberFormatImpl(icu::Locale& locale, icu::number::LocalizedNumberFormatter formatter, bool is_unit)
        : m_locale(locale)
        , m_formatter(move(formatter))
        , m_is_unit(is_unit)
    {
    }

    virtual ~NumberFormatImpl() override = default;

    virtual Utf16String format(Value const& value) const override
    {
        UErrorCode status = U_ZERO_ERROR;

        auto formatted = format_impl(value);
        if (!formatted.has_value())
            return {};

        auto result = formatted->toTempString(status);
        if (icu_failure(status))
            return {};

        return icu_string_to_utf16_string(result);
    }

    virtual Vector<Partition> format_to_parts(Value const& value) const override
    {
        auto formatted = format_impl(value);
        if (!formatted.has_value())
            return {};

        return format_to_parts_impl(formatted, value, value);
    }

    virtual Utf16String format_range(Value const& start, Value const& end) const override
    {
        UErrorCode status = U_ZERO_ERROR;

        auto formatted = format_range_impl(start, end);
        if (!formatted.has_value())
            return {};

        auto result = formatted->toTempString(status);
        if (icu_failure(status))
            return {};

        return icu_string_to_utf16_string(result);
    }

    virtual Vector<Partition> format_range_to_parts(Value const& start, Value const& end) const override
    {
        auto formatted = format_range_impl(start, end);
        if (!formatted.has_value())
            return {};

        return format_to_parts_impl(formatted, start, end);
    }

    virtual void create_plural_rules(PluralForm plural_form) override
    {
        UErrorCode status = U_ZERO_ERROR;
        VERIFY(!m_plural_rules);

        m_plural_rules = adopt_own(*icu::PluralRules::forLocale(m_locale, icu_plural_type(plural_form), status));
        verify_icu_success(status);
    }

    virtual PluralCategory select_plural(Value const& value) const override
    {
        UErrorCode status = U_ZERO_ERROR;
        VERIFY(m_plural_rules);

        auto formatted = format_impl(value);
        if (!formatted.has_value())
            return PluralCategory::Other;

        auto result = m_plural_rules->select(*formatted, status);
        if (icu_failure(status))
            return PluralCategory::Other;

        return plural_category_from_string(icu_string_to_utf16_view(result));
    }

    virtual PluralCategory select_plural_range(Value const& start, Value const& end) const override
    {
        UErrorCode status = U_ZERO_ERROR;
        VERIFY(m_plural_rules);

        auto formatted = format_range_impl(start, end);
        if (!formatted.has_value())
            return PluralCategory::Other;

        auto [formatted_start, formatted_end] = formatted->getDecimalNumbers<StringBuilder>(status);
        if (icu_failure(status))
            return PluralCategory::Other;

        if (formatted_start.string_view() == formatted_end.string_view())
            return select_plural(start);

        auto result = m_plural_rules->select(*formatted, status);
        if (icu_failure(status))
            return PluralCategory::Other;

        return plural_category_from_string(icu_string_to_utf16_view(result));
    }

    virtual Vector<PluralCategory> available_plural_categories() const override
    {
        UErrorCode status = U_ZERO_ERROR;
        VERIFY(m_plural_rules);

        auto keywords = adopt_own_if_nonnull(m_plural_rules->getKeywords(status));
        if (icu_failure(status))
            return {};

        Vector<PluralCategory> result;

        while (true) {
            i32 length = 0;
            auto const* category = keywords->unext(&length, status);

            if (icu_failure(status) || category == nullptr)
                break;

            result.append(plural_category_from_string({ category, static_cast<size_t>(length) }));
        }

        quick_sort(result);
        return result;
    }

private:
    struct DecimalStringPiece {
        String utf8_storage;
        icu::StringPiece string_piece;
    };

    static DecimalStringPiece decimal_string_piece(Utf16String const& number)
    {
        auto number_view = number.utf16_view();

        if (number_view.has_ascii_storage()) {
            auto bytes = number_view.bytes();
            return { {}, { reinterpret_cast<char const*>(bytes.data()), static_cast<i32>(bytes.size()) } };
        }

        DecimalStringPiece result;
        result.utf8_storage = MUST(number_view.to_utf8());
        result.string_piece = icu_string_piece(result.utf8_storage);
        return result;
    }

    static icu::Formattable value_to_formattable(Value const& value)
    {
        UErrorCode status = U_ZERO_ERROR;

        auto formattable = value.visit(
            [&](double number) { return icu::Formattable { number }; },
            [&](Utf16String const& number) {
                auto decimal_number = decimal_string_piece(number);
                return icu::Formattable(decimal_number.string_piece, status);
            });
        verify_icu_success(status);

        return formattable;
    }

    Optional<icu::number::FormattedNumber> format_impl(Value const& value) const
    {
        UErrorCode status = U_ZERO_ERROR;

        auto formatted = value.visit(
            [&](double number) {
                return m_formatter.formatDouble(number, status);
            },
            [&](Utf16String const& number) {
                auto decimal_number = decimal_string_piece(number);
                return m_formatter.formatDecimal(decimal_number.string_piece, status);
            });

        if (icu_failure(status))
            return {};

        return formatted;
    }

    Optional<icu::number::FormattedNumberRange> format_range_impl(Value const& start, Value const& end) const
    {
        UErrorCode status = U_ZERO_ERROR;

        if (!m_range_formatter.has_value()) {
            auto skeleton = icu::number::NumberFormatter::forSkeleton(m_formatter.toSkeleton(status), status);
            if (icu_failure(status))
                return {};

            auto formatter = icu::number::UnlocalizedNumberRangeFormatter().numberFormatterBoth(move(skeleton)).locale(m_locale);
            if (icu_failure(status))
                return {};

            m_range_formatter = move(formatter);
        }

        auto formattable_start = value_to_formattable(start);
        auto formattable_end = value_to_formattable(end);

        auto formatted = m_range_formatter->formatFormattableRange(formattable_start, formattable_end, status);
        if (icu_failure(status))
            return {};

        return formatted;
    }

    template<typename Formatted>
    Vector<Partition> format_to_parts_impl(Formatted const& formatted, Value const& start, Value const& end) const
    {
        UErrorCode status = U_ZERO_ERROR;

        auto formatted_number = formatted->toTempString(status);
        if (icu_failure(status))
            return {};

        Vector<PartitionRange> ranges;
        ranges.empend(PartitionRange::LITERAL_FIELD, 0, formatted_number.length());

        icu::ConstrainedFieldPosition position;
        Optional<PartitionRange> start_range;
        Optional<PartitionRange> end_range;

        while (static_cast<bool>(formatted->nextPosition(position, status)) && icu_success(status)) {
            if (position.getCategory() == UFIELD_CATEGORY_NUMBER_RANGE_SPAN) {
                auto& range = position.getField() == 0 ? start_range : end_range;
                range = PartitionRange { position.getField(), position.getStart(), position.getLimit() };
            } else {
                ranges.empend(position.getField(), position.getStart(), position.getLimit());
            }
        }

        flatten_partitions(ranges);

        auto apply_to_partition = [&](Partition& partition, auto field, auto index) {
            if (start_range.has_value() && start_range->contains(index)) {
                partition.type = icu_number_format_field_to_string(field, start, m_is_unit);
                partition.source = "startRange"_utf16;
                return;
            }

            if (end_range.has_value() && end_range->contains(index)) {
                partition.type = icu_number_format_field_to_string(field, end, m_is_unit);
                partition.source = "endRange"_utf16;
                return;
            }

            partition.type = icu_number_format_field_to_string(field, end, m_is_unit);
            partition.source = "shared"_utf16;
        };

        Vector<Partition> result;
        result.ensure_capacity(ranges.size());

        for (auto const& range : ranges) {
            auto value = formatted_number.tempSubStringBetween(range.start, range.end);

            Partition partition;
            partition.value = icu_string_to_utf16_string(value);
            apply_to_partition(partition, range.field, range.start);

            result.unchecked_append(move(partition));
        }

        return result;
    }

    icu::Locale& m_locale;

    icu::number::LocalizedNumberFormatter m_formatter;
    mutable Optional<icu::number::LocalizedNumberRangeFormatter> m_range_formatter;

    OwnPtr<icu::PluralRules> m_plural_rules;

    bool m_is_unit { false };
};

NonnullOwnPtr<NumberFormat> NumberFormat::create(
    Utf16View locale,
    DisplayOptions const& display_options,
    RoundingOptions const& rounding_options)
{
    auto locale_data = LocaleData::for_locale(locale.bytes());
    VERIFY(locale_data.has_value());

    auto formatter = icu::number::NumberFormatter::withLocale(locale_data->locale());
    apply_display_options(formatter, display_options);
    apply_rounding_options(formatter, rounding_options);

    bool is_unit = display_options.style == NumberFormatStyle::Unit;
    return adopt_own(*new NumberFormatImpl(locale_data->locale(), move(formatter), is_unit));
}

}
