Adding upstream version 115.7.0esr.upstream/115.7.0esrupstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>

1 files changed, 826 insertions, 0 deletions

diff --git a/intl/icu/source/common/localematcher.cpp b/intl/icu/source/common/localematcher.cpp
new file mode 100644
index 0000000000..5f8c703df7
--- /dev/null
+++ b/intl/icu/source/common/localematcher.cpp
@@ -0,0 +1,826 @@
+// © 2019 and later: Unicode, Inc. and others.
+// License & terms of use: http://www.unicode.org/copyright.html
+
+// localematcher.cpp
+// created: 2019may08 Markus W. Scherer
+
+#include "unicode/utypes.h"
+#include "unicode/localebuilder.h"
+#include "unicode/localematcher.h"
+#include "unicode/locid.h"
+#include "unicode/stringpiece.h"
+#include "unicode/uloc.h"
+#include "unicode/uobject.h"
+#include "cstring.h"
+#include "localeprioritylist.h"
+#include "loclikelysubtags.h"
+#include "locdistance.h"
+#include "lsr.h"
+#include "uassert.h"
+#include "uhash.h"
+#include "ustr_imp.h"
+#include "uvector.h"
+
+#define UND_LSR LSR("und", "", "", LSR::EXPLICIT_LSR)
+
+/**
+ * Indicator for the lifetime of desired-locale objects passed into the LocaleMatcher.
+ *
+ * @draft ICU 65
+ */
+enum ULocMatchLifetime {
+    /**
+     * Locale objects are temporary.
+     * The matcher will make a copy of a locale that will be used beyond one function call.
+     *
+     * @draft ICU 65
+     */
+    ULOCMATCH_TEMPORARY_LOCALES,
+    /**
+     * Locale objects are stored at least as long as the matcher is used.
+     * The matcher will keep only a pointer to a locale that will be used beyond one function call,
+     * avoiding a copy.
+     *
+     * @draft ICU 65
+     */
+    ULOCMATCH_STORED_LOCALES  // TODO: permanent? cached? clone?
+};
+#ifndef U_IN_DOXYGEN
+typedef enum ULocMatchLifetime ULocMatchLifetime;
+#endif
+
+U_NAMESPACE_BEGIN
+
+LocaleMatcher::Result::Result(LocaleMatcher::Result &&src) noexcept :
+        desiredLocale(src.desiredLocale),
+        supportedLocale(src.supportedLocale),
+        desiredIndex(src.desiredIndex),
+        supportedIndex(src.supportedIndex),
+        desiredIsOwned(src.desiredIsOwned) {
+    if (desiredIsOwned) {
+        src.desiredLocale = nullptr;
+        src.desiredIndex = -1;
+        src.desiredIsOwned = false;
+    }
+}
+
+LocaleMatcher::Result::~Result() {
+    if (desiredIsOwned) {
+        delete desiredLocale;
+    }
+}
+
+LocaleMatcher::Result &LocaleMatcher::Result::operator=(LocaleMatcher::Result &&src) noexcept {
+    this->~Result();
+
+    desiredLocale = src.desiredLocale;
+    supportedLocale = src.supportedLocale;
+    desiredIndex = src.desiredIndex;
+    supportedIndex = src.supportedIndex;
+    desiredIsOwned = src.desiredIsOwned;
+
+    if (desiredIsOwned) {
+        src.desiredLocale = nullptr;
+        src.desiredIndex = -1;
+        src.desiredIsOwned = false;
+    }
+    return *this;
+}
+
+Locale LocaleMatcher::Result::makeResolvedLocale(UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode) || supportedLocale == nullptr) {
+        return Locale::getRoot();
+    }
+    const Locale *bestDesired = getDesiredLocale();
+    if (bestDesired == nullptr || *supportedLocale == *bestDesired) {
+        return *supportedLocale;
+    }
+    LocaleBuilder b;
+    b.setLocale(*supportedLocale);
+
+    // Copy the region from bestDesired, if there is one.
+    const char *region = bestDesired->getCountry();
+    if (*region != 0) {
+        b.setRegion(region);
+    }
+
+    // Copy the variants from bestDesired, if there are any.
+    // Note that this will override any supportedLocale variants.
+    // For example, "sco-ulster-fonipa" + "...-fonupa" => "sco-fonupa" (replacing ulster).
+    const char *variants = bestDesired->getVariant();
+    if (*variants != 0) {
+        b.setVariant(variants);
+    }
+
+    // Copy the extensions from bestDesired, if there are any.
+    // C++ note: The following note, copied from Java, may not be true,
+    // as long as C++ copies by legacy ICU keyword, not by extension singleton.
+    // Note that this will override any supportedLocale extensions.
+    // For example, "th-u-nu-latn-ca-buddhist" + "...-u-nu-native" => "th-u-nu-native"
+    // (replacing calendar).
+    b.copyExtensionsFrom(*bestDesired, errorCode);
+    return b.build(errorCode);
+}
+
+LocaleMatcher::Builder::Builder(LocaleMatcher::Builder &&src) noexcept :
+        errorCode_(src.errorCode_),
+        supportedLocales_(src.supportedLocales_),
+        thresholdDistance_(src.thresholdDistance_),
+        demotion_(src.demotion_),
+        defaultLocale_(src.defaultLocale_),
+        withDefault_(src.withDefault_),
+        favor_(src.favor_),
+        direction_(src.direction_) {
+    src.supportedLocales_ = nullptr;
+    src.defaultLocale_ = nullptr;
+}
+
+LocaleMatcher::Builder::~Builder() {
+    delete supportedLocales_;
+    delete defaultLocale_;
+    delete maxDistanceDesired_;
+    delete maxDistanceSupported_;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::operator=(LocaleMatcher::Builder &&src) noexcept {
+    this->~Builder();
+
+    errorCode_ = src.errorCode_;
+    supportedLocales_ = src.supportedLocales_;
+    thresholdDistance_ = src.thresholdDistance_;
+    demotion_ = src.demotion_;
+    defaultLocale_ = src.defaultLocale_;
+    withDefault_ = src.withDefault_,
+    favor_ = src.favor_;
+    direction_ = src.direction_;
+
+    src.supportedLocales_ = nullptr;
+    src.defaultLocale_ = nullptr;
+    return *this;
+}
+
+void LocaleMatcher::Builder::clearSupportedLocales() {
+    if (supportedLocales_ != nullptr) {
+        supportedLocales_->removeAllElements();
+    }
+}
+
+bool LocaleMatcher::Builder::ensureSupportedLocaleVector() {
+    if (U_FAILURE(errorCode_)) { return false; }
+    if (supportedLocales_ != nullptr) { return true; }
+    LocalPointer<UVector> lpSupportedLocales(new UVector(uprv_deleteUObject, nullptr, errorCode_), errorCode_);
+    if (U_FAILURE(errorCode_)) { return false; }
+    supportedLocales_ = lpSupportedLocales.orphan();
+    return true;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocalesFromListString(
+        StringPiece locales) {
+    LocalePriorityList list(locales, errorCode_);
+    if (U_FAILURE(errorCode_)) { return *this; }
+    clearSupportedLocales();
+    if (!ensureSupportedLocaleVector()) { return *this; }
+    int32_t length = list.getLengthIncludingRemoved();
+    for (int32_t i = 0; i < length; ++i) {
+        Locale *locale = list.orphanLocaleAt(i);
+        if (locale == nullptr) { continue; }
+        supportedLocales_->adoptElement(locale, errorCode_);
+        if (U_FAILURE(errorCode_)) {
+            break;
+        }
+    }
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setSupportedLocales(Locale::Iterator &locales) {
+    if (ensureSupportedLocaleVector()) {
+        clearSupportedLocales();
+        while (locales.hasNext() && U_SUCCESS(errorCode_)) {
+            const Locale &locale = locales.next();
+            LocalPointer<Locale> clone (locale.clone(), errorCode_);
+            supportedLocales_->adoptElement(clone.orphan(), errorCode_);
+        }
+    }
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::addSupportedLocale(const Locale &locale) {
+    if (ensureSupportedLocaleVector()) {
+        LocalPointer<Locale> clone(locale.clone(), errorCode_);
+        supportedLocales_->adoptElement(clone.orphan(), errorCode_);
+    }
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setNoDefaultLocale() {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    delete defaultLocale_;
+    defaultLocale_ = nullptr;
+    withDefault_ = false;
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setDefaultLocale(const Locale *defaultLocale) {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    Locale *clone = nullptr;
+    if (defaultLocale != nullptr) {
+        clone = defaultLocale->clone();
+        if (clone == nullptr) {
+            errorCode_ = U_MEMORY_ALLOCATION_ERROR;
+            return *this;
+        }
+    }
+    delete defaultLocale_;
+    defaultLocale_ = clone;
+    withDefault_ = true;
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setFavorSubtag(ULocMatchFavorSubtag subtag) {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    favor_ = subtag;
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setDemotionPerDesiredLocale(ULocMatchDemotion demotion) {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    demotion_ = demotion;
+    return *this;
+}
+
+LocaleMatcher::Builder &LocaleMatcher::Builder::setMaxDistance(const Locale &desired,
+                                                               const Locale &supported) {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    Locale *desiredClone = desired.clone();
+    Locale *supportedClone = supported.clone();
+    if (desiredClone == nullptr || supportedClone == nullptr) {
+        delete desiredClone;  // in case only one could not be allocated
+        delete supportedClone;
+        errorCode_ = U_MEMORY_ALLOCATION_ERROR;
+        return *this;
+    }
+    delete maxDistanceDesired_;
+    delete maxDistanceSupported_;
+    maxDistanceDesired_ = desiredClone;
+    maxDistanceSupported_ = supportedClone;
+    return *this;
+}
+
+#if 0
+/**
+ * <i>Internal only!</i>
+ *
+ * @param thresholdDistance the thresholdDistance to set, with -1 = default
+ * @return this Builder object
+ * @internal
+ * @deprecated This API is ICU internal only.
+ */
+@Deprecated
+LocaleMatcher::Builder &LocaleMatcher::Builder::internalSetThresholdDistance(int32_t thresholdDistance) {
+    if (U_FAILURE(errorCode_)) { return *this; }
+    if (thresholdDistance > 100) {
+        thresholdDistance = 100;
+    }
+    thresholdDistance_ = thresholdDistance;
+    return *this;
+}
+#endif
+
+UBool LocaleMatcher::Builder::copyErrorTo(UErrorCode &outErrorCode) const {
+    if (U_FAILURE(outErrorCode)) { return true; }
+    if (U_SUCCESS(errorCode_)) { return false; }
+    outErrorCode = errorCode_;
+    return true;
+}
+
+LocaleMatcher LocaleMatcher::Builder::build(UErrorCode &errorCode) const {
+    if (U_SUCCESS(errorCode) && U_FAILURE(errorCode_)) {
+        errorCode = errorCode_;
+    }
+    return LocaleMatcher(*this, errorCode);
+}
+
+namespace {
+
+LSR getMaximalLsrOrUnd(const XLikelySubtags &likelySubtags, const Locale &locale,
+                       UErrorCode &errorCode) {
+    if (U_FAILURE(errorCode) || locale.isBogus() || *locale.getName() == 0 /* "und" */) {
+        return UND_LSR;
+    } else {
+        return likelySubtags.makeMaximizedLsrFrom(locale, errorCode);
+    }
+}
+
+int32_t hashLSR(const UHashTok token) {
+    const LSR *lsr = static_cast<const LSR *>(token.pointer);
+    return lsr->hashCode;
+}
+
+UBool compareLSRs(const UHashTok t1, const UHashTok t2) {
+    const LSR *lsr1 = static_cast<const LSR *>(t1.pointer);
+    const LSR *lsr2 = static_cast<const LSR *>(t2.pointer);
+    return *lsr1 == *lsr2;
+}
+
+}  // namespace
+
+int32_t LocaleMatcher::putIfAbsent(const LSR &lsr, int32_t i, int32_t suppLength,
+                                   UErrorCode &errorCode) {
+    if (U_FAILURE(errorCode)) { return suppLength; }
+    if (!uhash_containsKey(supportedLsrToIndex, &lsr)) {
+        uhash_putiAllowZero(supportedLsrToIndex, const_cast<LSR *>(&lsr), i, &errorCode);
+        if (U_SUCCESS(errorCode)) {
+            supportedLSRs[suppLength] = &lsr;
+            supportedIndexes[suppLength++] = i;
+        }
+    }
+    return suppLength;
+}
+
+LocaleMatcher::LocaleMatcher(const Builder &builder, UErrorCode &errorCode) :
+        likelySubtags(*XLikelySubtags::getSingleton(errorCode)),
+        localeDistance(*LocaleDistance::getSingleton(errorCode)),
+        thresholdDistance(builder.thresholdDistance_),
+        demotionPerDesiredLocale(0),
+        favorSubtag(builder.favor_),
+        direction(builder.direction_),
+        supportedLocales(nullptr), lsrs(nullptr), supportedLocalesLength(0),
+        supportedLsrToIndex(nullptr),
+        supportedLSRs(nullptr), supportedIndexes(nullptr), supportedLSRsLength(0),
+        ownedDefaultLocale(nullptr), defaultLocale(nullptr) {
+    if (U_FAILURE(errorCode)) { return; }
+    const Locale *def = builder.defaultLocale_;
+    LSR builderDefaultLSR;
+    const LSR *defLSR = nullptr;
+    if (def != nullptr) {
+        ownedDefaultLocale = def->clone();
+        if (ownedDefaultLocale == nullptr) {
+            errorCode = U_MEMORY_ALLOCATION_ERROR;
+            return;
+        }
+        def = ownedDefaultLocale;
+        builderDefaultLSR = getMaximalLsrOrUnd(likelySubtags, *def, errorCode);
+        if (U_FAILURE(errorCode)) { return; }
+        defLSR = &builderDefaultLSR;
+    }
+    supportedLocalesLength = builder.supportedLocales_ != nullptr ?
+        builder.supportedLocales_->size() : 0;
+    if (supportedLocalesLength > 0) {
+        // Store the supported locales in input order,
+        // so that when different types are used (e.g., language tag strings)
+        // we can return those by parallel index.
+        supportedLocales = static_cast<const Locale **>(
+            uprv_malloc(supportedLocalesLength * sizeof(const Locale *)));
+        // Supported LRSs in input order.
+        // In C++, we store these permanently to simplify ownership management
+        // in the hash tables. Duplicate LSRs (if any) are unused overhead.
+        lsrs = new LSR[supportedLocalesLength];
+        if (supportedLocales == nullptr || lsrs == nullptr) {
+            errorCode = U_MEMORY_ALLOCATION_ERROR;
+            return;
+        }
+        // If the constructor fails partway, we need null pointers for destructibility.
+        uprv_memset(supportedLocales, 0, supportedLocalesLength * sizeof(const Locale *));
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
+            const Locale &locale = *static_cast<Locale *>(builder.supportedLocales_->elementAt(i));
+            supportedLocales[i] = locale.clone();
+            if (supportedLocales[i] == nullptr) {
+                errorCode = U_MEMORY_ALLOCATION_ERROR;
+                return;
+            }
+            const Locale &supportedLocale = *supportedLocales[i];
+            LSR &lsr = lsrs[i] = getMaximalLsrOrUnd(likelySubtags, supportedLocale, errorCode);
+            lsr.setHashCode();
+            if (U_FAILURE(errorCode)) { return; }
+        }
+
+        // We need an unordered map from LSR to first supported locale with that LSR,
+        // and an ordered list of (LSR, supported index) for
+        // the supported locales in the following order:
+        // 1. Default locale, if it is supported.
+        // 2. Priority locales (aka "paradigm locales") in builder order.
+        // 3. Remaining locales in builder order.
+        supportedLsrToIndex = uhash_openSize(hashLSR, compareLSRs, uhash_compareLong,
+                                             supportedLocalesLength, &errorCode);
+        if (U_FAILURE(errorCode)) { return; }
+        supportedLSRs = static_cast<const LSR **>(
+            uprv_malloc(supportedLocalesLength * sizeof(const LSR *)));
+        supportedIndexes = static_cast<int32_t *>(
+            uprv_malloc(supportedLocalesLength * sizeof(int32_t)));
+        if (supportedLSRs == nullptr || supportedIndexes == nullptr) {
+            errorCode = U_MEMORY_ALLOCATION_ERROR;
+            return;
+        }
+        int32_t suppLength = 0;
+        // Determine insertion order.
+        // Add locales immediately that are equivalent to the default.
+        MaybeStackArray<int8_t, 100> order(supportedLocalesLength, errorCode);
+        if (U_FAILURE(errorCode)) { return; }
+        int32_t numParadigms = 0;
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
+            const Locale &locale = *supportedLocales[i];
+            const LSR &lsr = lsrs[i];
+            if (defLSR == nullptr && builder.withDefault_) {
+                // Implicit default locale = first supported locale, if not turned off.
+                U_ASSERT(i == 0);
+                def = &locale;
+                defLSR = &lsr;
+                order[i] = 1;
+                suppLength = putIfAbsent(lsr, 0, suppLength, errorCode);
+            } else if (defLSR != nullptr && lsr.isEquivalentTo(*defLSR)) {
+                order[i] = 1;
+                suppLength = putIfAbsent(lsr, i, suppLength, errorCode);
+            } else if (localeDistance.isParadigmLSR(lsr)) {
+                order[i] = 2;
+                ++numParadigms;
+            } else {
+                order[i] = 3;
+            }
+            if (U_FAILURE(errorCode)) { return; }
+        }
+        // Add supported paradigm locales.
+        int32_t paradigmLimit = suppLength + numParadigms;
+        for (int32_t i = 0; i < supportedLocalesLength && suppLength < paradigmLimit; ++i) {
+            if (order[i] == 2) {
+                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode);
+            }
+        }
+        // Add remaining supported locales.
+        for (int32_t i = 0; i < supportedLocalesLength; ++i) {
+            if (order[i] == 3) {
+                suppLength = putIfAbsent(lsrs[i], i, suppLength, errorCode);
+            }
+        }
+        supportedLSRsLength = suppLength;
+        // If supportedLSRsLength < supportedLocalesLength then
+        // we waste as many array slots as there are duplicate supported LSRs,
+        // but the amount of wasted space is small as long as there are few duplicates.
+    }
+
+    defaultLocale = def;
+
+    if (builder.demotion_ == ULOCMATCH_DEMOTION_REGION) {
+        demotionPerDesiredLocale = localeDistance.getDefaultDemotionPerDesiredLocale();
+    }
+
+    if (thresholdDistance >= 0) {
+        // already copied
+    } else if (builder.maxDistanceDesired_ != nullptr) {
+        LSR suppLSR = getMaximalLsrOrUnd(likelySubtags, *builder.maxDistanceSupported_, errorCode);
+        const LSR *pSuppLSR = &suppLSR;
+        int32_t indexAndDistance = localeDistance.getBestIndexAndDistance(
+                getMaximalLsrOrUnd(likelySubtags, *builder.maxDistanceDesired_, errorCode),
+                &pSuppLSR, 1,
+                LocaleDistance::shiftDistance(100), favorSubtag, direction);
+        if (U_SUCCESS(errorCode)) {
+            // +1 for an exclusive threshold from an inclusive max.
+            thresholdDistance = LocaleDistance::getDistanceFloor(indexAndDistance) + 1;
+        } else {
+            thresholdDistance = 0;
+        }
+    } else {
+        thresholdDistance = localeDistance.getDefaultScriptDistance();
+    }
+}
+
+LocaleMatcher::LocaleMatcher(LocaleMatcher &&src) noexcept :
+        likelySubtags(src.likelySubtags),
+        localeDistance(src.localeDistance),
+        thresholdDistance(src.thresholdDistance),
+        demotionPerDesiredLocale(src.demotionPerDesiredLocale),
+        favorSubtag(src.favorSubtag),
+        direction(src.direction),
+        supportedLocales(src.supportedLocales), lsrs(src.lsrs),
+        supportedLocalesLength(src.supportedLocalesLength),
+        supportedLsrToIndex(src.supportedLsrToIndex),
+        supportedLSRs(src.supportedLSRs),
+        supportedIndexes(src.supportedIndexes),
+        supportedLSRsLength(src.supportedLSRsLength),
+        ownedDefaultLocale(src.ownedDefaultLocale), defaultLocale(src.defaultLocale) {
+    src.supportedLocales = nullptr;
+    src.lsrs = nullptr;
+    src.supportedLocalesLength = 0;
+    src.supportedLsrToIndex = nullptr;
+    src.supportedLSRs = nullptr;
+    src.supportedIndexes = nullptr;
+    src.supportedLSRsLength = 0;
+    src.ownedDefaultLocale = nullptr;
+    src.defaultLocale = nullptr;
+}
+
+LocaleMatcher::~LocaleMatcher() {
+    for (int32_t i = 0; i < supportedLocalesLength; ++i) {
+        delete supportedLocales[i];
+    }
+    uprv_free(supportedLocales);
+    delete[] lsrs;
+    uhash_close(supportedLsrToIndex);
+    uprv_free(supportedLSRs);
+    uprv_free(supportedIndexes);
+    delete ownedDefaultLocale;
+}
+
+LocaleMatcher &LocaleMatcher::operator=(LocaleMatcher &&src) noexcept {
+    this->~LocaleMatcher();
+
+    thresholdDistance = src.thresholdDistance;
+    demotionPerDesiredLocale = src.demotionPerDesiredLocale;
+    favorSubtag = src.favorSubtag;
+    direction = src.direction;
+    supportedLocales = src.supportedLocales;
+    lsrs = src.lsrs;
+    supportedLocalesLength = src.supportedLocalesLength;
+    supportedLsrToIndex = src.supportedLsrToIndex;
+    supportedLSRs = src.supportedLSRs;
+    supportedIndexes = src.supportedIndexes;
+    supportedLSRsLength = src.supportedLSRsLength;
+    ownedDefaultLocale = src.ownedDefaultLocale;
+    defaultLocale = src.defaultLocale;
+
+    src.supportedLocales = nullptr;
+    src.lsrs = nullptr;
+    src.supportedLocalesLength = 0;
+    src.supportedLsrToIndex = nullptr;
+    src.supportedLSRs = nullptr;
+    src.supportedIndexes = nullptr;
+    src.supportedLSRsLength = 0;
+    src.ownedDefaultLocale = nullptr;
+    src.defaultLocale = nullptr;
+    return *this;
+}
+
+class LocaleLsrIterator {
+public:
+    LocaleLsrIterator(const XLikelySubtags &likelySubtags, Locale::Iterator &locales,
+                      ULocMatchLifetime lifetime) :
+            likelySubtags(likelySubtags), locales(locales), lifetime(lifetime) {}
+
+    ~LocaleLsrIterator() {
+        if (lifetime == ULOCMATCH_TEMPORARY_LOCALES) {
+            delete remembered;
+        }
+    }
+
+    bool hasNext() const {
+        return locales.hasNext();
+    }
+
+    LSR next(UErrorCode &errorCode) {
+        current = &locales.next();
+        return getMaximalLsrOrUnd(likelySubtags, *current, errorCode);
+    }
+
+    void rememberCurrent(int32_t desiredIndex, UErrorCode &errorCode) {
+        if (U_FAILURE(errorCode)) { return; }
+        bestDesiredIndex = desiredIndex;
+        if (lifetime == ULOCMATCH_STORED_LOCALES) {
+            remembered = current;
+        } else {
+            // ULOCMATCH_TEMPORARY_LOCALES
+            delete remembered;
+            remembered = new Locale(*current);
+            if (remembered == nullptr) {
+                errorCode = U_MEMORY_ALLOCATION_ERROR;
+            }
+        }
+    }
+
+    const Locale *orphanRemembered() {
+        const Locale *rem = remembered;
+        remembered = nullptr;
+        return rem;
+    }
+
+    int32_t getBestDesiredIndex() const {
+        return bestDesiredIndex;
+    }
+
+private:
+    const XLikelySubtags &likelySubtags;
+    Locale::Iterator &locales;
+    ULocMatchLifetime lifetime;
+    const Locale *current = nullptr, *remembered = nullptr;
+    int32_t bestDesiredIndex = -1;
+};
+
+const Locale *LocaleMatcher::getBestMatch(const Locale &desiredLocale, UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode)) { return nullptr; }
+    int32_t suppIndex = getBestSuppIndex(
+        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode),
+        nullptr, errorCode);
+    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale;
+}
+
+const Locale *LocaleMatcher::getBestMatch(Locale::Iterator &desiredLocales,
+                                          UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode)) { return nullptr; }
+    if (!desiredLocales.hasNext()) {
+        return defaultLocale;
+    }
+    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES);
+    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode);
+    return U_SUCCESS(errorCode) && suppIndex >= 0 ? supportedLocales[suppIndex] : defaultLocale;
+}
+
+const Locale *LocaleMatcher::getBestMatchForListString(
+        StringPiece desiredLocaleList, UErrorCode &errorCode) const {
+    LocalePriorityList list(desiredLocaleList, errorCode);
+    LocalePriorityList::Iterator iter = list.iterator();
+    return getBestMatch(iter, errorCode);
+}
+
+LocaleMatcher::Result LocaleMatcher::getBestMatchResult(
+        const Locale &desiredLocale, UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode)) {
+        return Result(nullptr, defaultLocale, -1, -1, false);
+    }
+    int32_t suppIndex = getBestSuppIndex(
+        getMaximalLsrOrUnd(likelySubtags, desiredLocale, errorCode),
+        nullptr, errorCode);
+    if (U_FAILURE(errorCode) || suppIndex < 0) {
+        return Result(nullptr, defaultLocale, -1, -1, false);
+    } else {
+        return Result(&desiredLocale, supportedLocales[suppIndex], 0, suppIndex, false);
+    }
+}
+
+LocaleMatcher::Result LocaleMatcher::getBestMatchResult(
+        Locale::Iterator &desiredLocales, UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode) || !desiredLocales.hasNext()) {
+        return Result(nullptr, defaultLocale, -1, -1, false);
+    }
+    LocaleLsrIterator lsrIter(likelySubtags, desiredLocales, ULOCMATCH_TEMPORARY_LOCALES);
+    int32_t suppIndex = getBestSuppIndex(lsrIter.next(errorCode), &lsrIter, errorCode);
+    if (U_FAILURE(errorCode) || suppIndex < 0) {
+        return Result(nullptr, defaultLocale, -1, -1, false);
+    } else {
+        return Result(lsrIter.orphanRemembered(), supportedLocales[suppIndex],
+                      lsrIter.getBestDesiredIndex(), suppIndex, true);
+    }
+}
+
+int32_t LocaleMatcher::getBestSuppIndex(LSR desiredLSR, LocaleLsrIterator *remainingIter,
+                                        UErrorCode &errorCode) const {
+    if (U_FAILURE(errorCode)) { return -1; }
+    int32_t desiredIndex = 0;
+    int32_t bestSupportedLsrIndex = -1;
+    for (int32_t bestShiftedDistance = LocaleDistance::shiftDistance(thresholdDistance);;) {
+        // Quick check for exact maximized LSR.
+        if (supportedLsrToIndex != nullptr) {
+            desiredLSR.setHashCode();
+            UBool found = false;
+            int32_t suppIndex = uhash_getiAndFound(supportedLsrToIndex, &desiredLSR, &found);
+            if (found) {
+                if (remainingIter != nullptr) {
+                    remainingIter->rememberCurrent(desiredIndex, errorCode);
+                }
+                return suppIndex;
+            }
+        }
+        int32_t bestIndexAndDistance = localeDistance.getBestIndexAndDistance(
+                desiredLSR, supportedLSRs, supportedLSRsLength,
+                bestShiftedDistance, favorSubtag, direction);
+        if (bestIndexAndDistance >= 0) {
+            bestShiftedDistance = LocaleDistance::getShiftedDistance(bestIndexAndDistance);
+            if (remainingIter != nullptr) {
+                remainingIter->rememberCurrent(desiredIndex, errorCode);
+                if (U_FAILURE(errorCode)) { return -1; }
+            }
+            bestSupportedLsrIndex = LocaleDistance::getIndex(bestIndexAndDistance);
+        }
+        if ((bestShiftedDistance -= LocaleDistance::shiftDistance(demotionPerDesiredLocale)) <= 0) {
+            break;
+        }
+        if (remainingIter == nullptr || !remainingIter->hasNext()) {
+            break;
+        }
+        desiredLSR = remainingIter->next(errorCode);
+        if (U_FAILURE(errorCode)) { return -1; }
+        ++desiredIndex;
+    }
+    if (bestSupportedLsrIndex < 0) {
+        // no good match
+        return -1;
+    }
+    return supportedIndexes[bestSupportedLsrIndex];
+}
+
+UBool LocaleMatcher::isMatch(const Locale &desired, const Locale &supported,
+                             UErrorCode &errorCode) const {
+    LSR suppLSR = getMaximalLsrOrUnd(likelySubtags, supported, errorCode);
+    if (U_FAILURE(errorCode)) { return 0; }
+    const LSR *pSuppLSR = &suppLSR;
+    int32_t indexAndDistance = localeDistance.getBestIndexAndDistance(
+            getMaximalLsrOrUnd(likelySubtags, desired, errorCode),
+            &pSuppLSR, 1,
+            LocaleDistance::shiftDistance(thresholdDistance), favorSubtag, direction);
+    return indexAndDistance >= 0;
+}
+
+double LocaleMatcher::internalMatch(const Locale &desired, const Locale &supported, UErrorCode &errorCode) const {
+    // Returns the inverse of the distance: That is, 1-distance(desired, supported).
+    LSR suppLSR = getMaximalLsrOrUnd(likelySubtags, supported, errorCode);
+    if (U_FAILURE(errorCode)) { return 0; }
+    const LSR *pSuppLSR = &suppLSR;
+    int32_t indexAndDistance = localeDistance.getBestIndexAndDistance(
+            getMaximalLsrOrUnd(likelySubtags, desired, errorCode),
+            &pSuppLSR, 1,
+            LocaleDistance::shiftDistance(thresholdDistance), favorSubtag, direction);
+    double distance = LocaleDistance::getDistanceDouble(indexAndDistance);
+    return (100.0 - distance) / 100.0;
+}
+
+U_NAMESPACE_END
+
+// uloc_acceptLanguage() --------------------------------------------------- ***
+
+U_NAMESPACE_USE
+
+namespace {
+
+class LocaleFromTag {
+public:
+    LocaleFromTag() : locale(Locale::getRoot()) {}
+    const Locale &operator()(const char *tag) { return locale = Locale(tag); }
+
+private:
+    // Store the locale in the converter, rather than return a reference to a temporary,
+    // or a value which could go out of scope with the caller's reference to it.
+    Locale locale;
+};
+
+int32_t acceptLanguage(UEnumeration &supportedLocales, Locale::Iterator &desiredLocales,
+                       char *dest, int32_t capacity, UAcceptResult *acceptResult,
+                       UErrorCode &errorCode) {
+    if (U_FAILURE(errorCode)) { return 0; }
+    LocaleMatcher::Builder builder;
+    const char *locString;
+    while ((locString = uenum_next(&supportedLocales, nullptr, &errorCode)) != nullptr) {
+        Locale loc(locString);
+        if (loc.isBogus()) {
+            errorCode = U_ILLEGAL_ARGUMENT_ERROR;
+            return 0;
+        }
+        builder.addSupportedLocale(loc);
+    }
+    LocaleMatcher matcher = builder.build(errorCode);
+    LocaleMatcher::Result result = matcher.getBestMatchResult(desiredLocales, errorCode);
+    if (U_FAILURE(errorCode)) { return 0; }
+    if (result.getDesiredIndex() >= 0) {
+        if (acceptResult != nullptr) {
+            *acceptResult = *result.getDesiredLocale() == *result.getSupportedLocale() ?
+                ULOC_ACCEPT_VALID : ULOC_ACCEPT_FALLBACK;
+        }
+        const char *bestStr = result.getSupportedLocale()->getName();
+        int32_t bestLength = (int32_t)uprv_strlen(bestStr);
+        if (bestLength <= capacity) {
+            uprv_memcpy(dest, bestStr, bestLength);
+        }
+        return u_terminateChars(dest, capacity, bestLength, &errorCode);
+    } else {
+        if (acceptResult != nullptr) {
+            *acceptResult = ULOC_ACCEPT_FAILED;
+        }
+        return u_terminateChars(dest, capacity, 0, &errorCode);
+    }
+}
+
+}  // namespace
+
+U_CAPI int32_t U_EXPORT2
+uloc_acceptLanguage(char *result, int32_t resultAvailable,
+                    UAcceptResult *outResult,
+                    const char **acceptList, int32_t acceptListCount,
+                    UEnumeration *availableLocales,
+                    UErrorCode *status) {
+    if (U_FAILURE(*status)) { return 0; }
+    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) ||
+            (acceptList == nullptr ? acceptListCount != 0 : acceptListCount < 0) ||
+            availableLocales == nullptr) {
+        *status = U_ILLEGAL_ARGUMENT_ERROR;
+        return 0;
+    }
+    LocaleFromTag converter;
+    Locale::ConvertingIterator<const char **, LocaleFromTag> desiredLocales(
+        acceptList, acceptList + acceptListCount, converter);
+    return acceptLanguage(*availableLocales, desiredLocales,
+                          result, resultAvailable, outResult, *status);
+}
+
+U_CAPI int32_t U_EXPORT2
+uloc_acceptLanguageFromHTTP(char *result, int32_t resultAvailable,
+                            UAcceptResult *outResult,
+                            const char *httpAcceptLanguage,
+                            UEnumeration *availableLocales,
+                            UErrorCode *status) {
+    if (U_FAILURE(*status)) { return 0; }
+    if ((result == nullptr ? resultAvailable != 0 : resultAvailable < 0) ||
+            httpAcceptLanguage == nullptr || availableLocales == nullptr) {
+        *status = U_ILLEGAL_ARGUMENT_ERROR;
+        return 0;
+    }
+    LocalePriorityList list(httpAcceptLanguage, *status);
+    LocalePriorityList::Iterator desiredLocales = list.iterator();
+    return acceptLanguage(*availableLocales, desiredLocales,
+                          result, resultAvailable, outResult, *status);
+}