// © 2019 and later: Unicode, Inc. and others. // License & terms of use: http://www.unicode.org/copyright.html // locdistance.cpp // created: 2019may08 Markus W. Scherer #include "unicode/utypes.h" #include "unicode/bytestrie.h" #include "unicode/localematcher.h" #include "unicode/locid.h" #include "unicode/uobject.h" #include "unicode/ures.h" #include "cstring.h" #include "locdistance.h" #include "loclikelysubtags.h" #include "uassert.h" #include "ucln_cmn.h" #include "uinvchar.h" #include "umutex.h" U_NAMESPACE_BEGIN namespace { /** * Bit flag used on the last character of a subtag in the trie. * Must be set consistently by the builder and the lookup code. */ constexpr int32_t END_OF_SUBTAG = 0x80; /** Distance value bit flag, set by the builder. */ constexpr int32_t DISTANCE_SKIP_SCRIPT = 0x80; /** Distance value bit flag, set by trieNext(). */ constexpr int32_t DISTANCE_IS_FINAL = 0x100; constexpr int32_t DISTANCE_IS_FINAL_OR_SKIP_SCRIPT = DISTANCE_IS_FINAL | DISTANCE_SKIP_SCRIPT; constexpr int32_t ABOVE_THRESHOLD = 100; // Indexes into array of distances. enum { IX_DEF_LANG_DISTANCE, IX_DEF_SCRIPT_DISTANCE, IX_DEF_REGION_DISTANCE, IX_MIN_REGION_DISTANCE, IX_LIMIT }; LocaleDistance *gLocaleDistance = nullptr; UInitOnce gInitOnce {}; UBool U_CALLCONV cleanup() { delete gLocaleDistance; gLocaleDistance = nullptr; gInitOnce.reset(); return true; } } // namespace void U_CALLCONV LocaleDistance::initLocaleDistance(UErrorCode &errorCode) { // This function is invoked only via umtx_initOnce(). U_ASSERT(gLocaleDistance == nullptr); const XLikelySubtags &likely = *XLikelySubtags::getSingleton(errorCode); if (U_FAILURE(errorCode)) { return; } const LocaleDistanceData &data = likely.getDistanceData(); if (data.distanceTrieBytes == nullptr || data.regionToPartitions == nullptr || data.partitions == nullptr || // ok if no paradigms data.distances == nullptr) { errorCode = U_MISSING_RESOURCE_ERROR; return; } gLocaleDistance = new LocaleDistance(data, likely); if (gLocaleDistance == nullptr) { errorCode = U_MEMORY_ALLOCATION_ERROR; return; } ucln_common_registerCleanup(UCLN_COMMON_LOCALE_DISTANCE, cleanup); } const LocaleDistance *LocaleDistance::getSingleton(UErrorCode &errorCode) { if (U_FAILURE(errorCode)) { return nullptr; } umtx_initOnce(gInitOnce, &LocaleDistance::initLocaleDistance, errorCode); return gLocaleDistance; } LocaleDistance::LocaleDistance(const LocaleDistanceData &data, const XLikelySubtags &likely) : likelySubtags(likely), trie(data.distanceTrieBytes), regionToPartitionsIndex(data.regionToPartitions), partitionArrays(data.partitions), paradigmLSRs(data.paradigms), paradigmLSRsLength(data.paradigmsLength), defaultLanguageDistance(data.distances[IX_DEF_LANG_DISTANCE]), defaultScriptDistance(data.distances[IX_DEF_SCRIPT_DISTANCE]), defaultRegionDistance(data.distances[IX_DEF_REGION_DISTANCE]), minRegionDistance(data.distances[IX_MIN_REGION_DISTANCE]) { // For the default demotion value, use the // default region distance between unrelated Englishes. // Thus, unless demotion is turned off, // a mere region difference for one desired locale // is as good as a perfect match for the next following desired locale. // As of CLDR 36, we have <languageMatch desired="en_*_*" supported="en_*_*" distance="5"/>. LSR en("en", "Latn", "US", LSR::EXPLICIT_LSR); LSR enGB("en", "Latn", "GB", LSR::EXPLICIT_LSR); const LSR *p_enGB = &enGB; int32_t indexAndDistance = getBestIndexAndDistance(en, &p_enGB, 1, shiftDistance(50), ULOCMATCH_FAVOR_LANGUAGE, ULOCMATCH_DIRECTION_WITH_ONE_WAY); defaultDemotionPerDesiredLocale = getDistanceFloor(indexAndDistance); } int32_t LocaleDistance::getBestIndexAndDistance( const LSR &desired, const LSR **supportedLSRs, int32_t supportedLSRsLength, int32_t shiftedThreshold, ULocMatchFavorSubtag favorSubtag, ULocMatchDirection direction) const { BytesTrie iter(trie); // Look up the desired language only once for all supported LSRs. // Its "distance" is either a match point value of 0, or a non-match negative value. // Note: The data builder verifies that there are no <*, supported> or <desired, *> rules. int32_t desLangDistance = trieNext(iter, desired.language, false); uint64_t desLangState = desLangDistance >= 0 && supportedLSRsLength > 1 ? iter.getState64() : 0; // Index of the supported LSR with the lowest distance. int32_t bestIndex = -1; // Cached lookup info from XLikelySubtags.compareLikely(). int32_t bestLikelyInfo = -1; for (int32_t slIndex = 0; slIndex < supportedLSRsLength; ++slIndex) { const LSR &supported = *supportedLSRs[slIndex]; bool star = false; int32_t distance = desLangDistance; if (distance >= 0) { U_ASSERT((distance & DISTANCE_IS_FINAL) == 0); if (slIndex != 0) { iter.resetToState64(desLangState); } distance = trieNext(iter, supported.language, true); } // Note: The data builder verifies that there are no rules with "any" (*) language and // real (non *) script or region subtags. // This means that if the lookup for either language fails we can use // the default distances without further lookups. int32_t flags; if (distance >= 0) { flags = distance & DISTANCE_IS_FINAL_OR_SKIP_SCRIPT; distance &= ~DISTANCE_IS_FINAL_OR_SKIP_SCRIPT; } else { // <*, *> if (uprv_strcmp(desired.language, supported.language) == 0) { distance = 0; } else { distance = defaultLanguageDistance; } flags = 0; star = true; } U_ASSERT(0 <= distance && distance <= 100); // Round up the shifted threshold (if fraction bits are not 0) // for comparison with un-shifted distances until we need fraction bits. // (If we simply shifted non-zero fraction bits away, then we might ignore a language // when it's really still a micro distance below the threshold.) int32_t roundedThreshold = (shiftedThreshold + DISTANCE_FRACTION_MASK) >> DISTANCE_SHIFT; // We implement "favor subtag" by reducing the language subtag distance // (unscientifically reducing it to a quarter of the normal value), // so that the script distance is relatively more important. // For example, given a default language distance of 80, we reduce it to 20, // which is below the default threshold of 50, which is the default script distance. if (favorSubtag == ULOCMATCH_FAVOR_SCRIPT) { distance >>= 2; } // Let distance == roundedThreshold pass until the tie-breaker logic // at the end of the loop. if (distance > roundedThreshold) { continue; } int32_t scriptDistance; if (star || flags != 0) { if (uprv_strcmp(desired.script, supported.script) == 0) { scriptDistance = 0; } else { scriptDistance = defaultScriptDistance; } } else { scriptDistance = getDesSuppScriptDistance(iter, iter.getState64(), desired.script, supported.script); flags = scriptDistance & DISTANCE_IS_FINAL; scriptDistance &= ~DISTANCE_IS_FINAL; } distance += scriptDistance; if (distance > roundedThreshold) { continue; } if (uprv_strcmp(desired.region, supported.region) == 0) { // regionDistance = 0 } else if (star || (flags & DISTANCE_IS_FINAL) != 0) { distance += defaultRegionDistance; } else { int32_t remainingThreshold = roundedThreshold - distance; if (minRegionDistance > remainingThreshold) { continue; } // From here on we know the regions are not equal. // Map each region to zero or more partitions. (zero = one non-matching string) // (Each array of single-character partition strings is encoded as one string.) // If either side has more than one, then we find the maximum distance. // This could be optimized by adding some more structure, but probably not worth it. distance += getRegionPartitionsDistance( iter, iter.getState64(), partitionsForRegion(desired), partitionsForRegion(supported), remainingThreshold); } int32_t shiftedDistance = shiftDistance(distance); if (shiftedDistance == 0) { // Distinguish between equivalent but originally unequal locales via an // additional micro distance. shiftedDistance |= (desired.flags ^ supported.flags); if (shiftedDistance < shiftedThreshold) { if (direction != ULOCMATCH_DIRECTION_ONLY_TWO_WAY || // Is there also a match when we swap desired/supported? isMatch(supported, desired, shiftedThreshold, favorSubtag)) { if (shiftedDistance == 0) { return slIndex << INDEX_SHIFT; } bestIndex = slIndex; shiftedThreshold = shiftedDistance; bestLikelyInfo = -1; } } } else { if (shiftedDistance < shiftedThreshold) { if (direction != ULOCMATCH_DIRECTION_ONLY_TWO_WAY || // Is there also a match when we swap desired/supported? isMatch(supported, desired, shiftedThreshold, favorSubtag)) { bestIndex = slIndex; shiftedThreshold = shiftedDistance; bestLikelyInfo = -1; } } else if (shiftedDistance == shiftedThreshold && bestIndex >= 0) { if (direction != ULOCMATCH_DIRECTION_ONLY_TWO_WAY || // Is there also a match when we swap desired/supported? isMatch(supported, desired, shiftedThreshold, favorSubtag)) { bestLikelyInfo = likelySubtags.compareLikely( supported, *supportedLSRs[bestIndex], bestLikelyInfo); if ((bestLikelyInfo & 1) != 0) { // This supported locale matches as well as the previous best match, // and neither matches perfectly, // but this one is "more likely" (has more-default subtags). bestIndex = slIndex; } } } } } return bestIndex >= 0 ? (bestIndex << INDEX_SHIFT) | shiftedThreshold : INDEX_NEG_1 | shiftDistance(ABOVE_THRESHOLD); } int32_t LocaleDistance::getDesSuppScriptDistance( BytesTrie &iter, uint64_t startState, const char *desired, const char *supported) { // Note: The data builder verifies that there are no <*, supported> or <desired, *> rules. int32_t distance = trieNext(iter, desired, false); if (distance >= 0) { distance = trieNext(iter, supported, true); } if (distance < 0) { UStringTrieResult result = iter.resetToState64(startState).next(u'*'); // <*, *> U_ASSERT(USTRINGTRIE_HAS_VALUE(result)); if (uprv_strcmp(desired, supported) == 0) { distance = 0; // same script } else { distance = iter.getValue(); U_ASSERT(distance >= 0); } if (result == USTRINGTRIE_FINAL_VALUE) { distance |= DISTANCE_IS_FINAL; } } return distance; } int32_t LocaleDistance::getRegionPartitionsDistance( BytesTrie &iter, uint64_t startState, const char *desiredPartitions, const char *supportedPartitions, int32_t threshold) { char desired = *desiredPartitions++; char supported = *supportedPartitions++; U_ASSERT(desired != 0 && supported != 0); // See if we have single desired/supported partitions, from NUL-terminated // partition strings without explicit length. bool suppLengthGt1 = *supportedPartitions != 0; // gt1: more than 1 character // equivalent to: if (desLength == 1 && suppLength == 1) if (*desiredPartitions == 0 && !suppLengthGt1) { // Fastpath for single desired/supported partitions. UStringTrieResult result = iter.next(uprv_invCharToAscii(desired) | END_OF_SUBTAG); if (USTRINGTRIE_HAS_NEXT(result)) { result = iter.next(uprv_invCharToAscii(supported) | END_OF_SUBTAG); if (USTRINGTRIE_HAS_VALUE(result)) { return iter.getValue(); } } return getFallbackRegionDistance(iter, startState); } const char *supportedStart = supportedPartitions - 1; // for restart of inner loop int32_t regionDistance = 0; // Fall back to * only once, not for each pair of partition strings. bool star = false; for (;;) { // Look up each desired-partition string only once, // not for each (desired, supported) pair. UStringTrieResult result = iter.next(uprv_invCharToAscii(desired) | END_OF_SUBTAG); if (USTRINGTRIE_HAS_NEXT(result)) { uint64_t desState = suppLengthGt1 ? iter.getState64() : 0; for (;;) { result = iter.next(uprv_invCharToAscii(supported) | END_OF_SUBTAG); int32_t d; if (USTRINGTRIE_HAS_VALUE(result)) { d = iter.getValue(); } else if (star) { d = 0; } else { d = getFallbackRegionDistance(iter, startState); star = true; } if (d > threshold) { return d; } else if (regionDistance < d) { regionDistance = d; } if ((supported = *supportedPartitions++) != 0) { iter.resetToState64(desState); } else { break; } } } else if (!star) { int32_t d = getFallbackRegionDistance(iter, startState); if (d > threshold) { return d; } else if (regionDistance < d) { regionDistance = d; } star = true; } if ((desired = *desiredPartitions++) != 0) { iter.resetToState64(startState); supportedPartitions = supportedStart; supported = *supportedPartitions++; } else { break; } } return regionDistance; } int32_t LocaleDistance::getFallbackRegionDistance(BytesTrie &iter, uint64_t startState) { #if U_DEBUG UStringTrieResult result = #endif iter.resetToState64(startState).next(u'*'); // <*, *> U_ASSERT(USTRINGTRIE_HAS_VALUE(result)); int32_t distance = iter.getValue(); U_ASSERT(distance >= 0); return distance; } int32_t LocaleDistance::trieNext(BytesTrie &iter, const char *s, bool wantValue) { uint8_t c; if ((c = *s) == 0) { return -1; // no empty subtags in the distance data } for (;;) { c = uprv_invCharToAscii(c); // EBCDIC: If *s is not an invariant character, // then c is now 0 and will simply not match anything, which is harmless. uint8_t next = *++s; if (next != 0) { if (!USTRINGTRIE_HAS_NEXT(iter.next(c))) { return -1; } } else { // last character of this subtag UStringTrieResult result = iter.next(c | END_OF_SUBTAG); if (wantValue) { if (USTRINGTRIE_HAS_VALUE(result)) { int32_t value = iter.getValue(); if (result == USTRINGTRIE_FINAL_VALUE) { value |= DISTANCE_IS_FINAL; } return value; } } else { if (USTRINGTRIE_HAS_NEXT(result)) { return 0; } } return -1; } c = next; } } UBool LocaleDistance::isParadigmLSR(const LSR &lsr) const { // Linear search for a very short list (length 6 as of 2019), // because we look for equivalence not equality, and // because it's easy. // If there are many paradigm LSRs we should use a hash set // with custom comparator and hasher. U_ASSERT(paradigmLSRsLength <= 15); for (int32_t i = 0; i < paradigmLSRsLength; ++i) { if (lsr.isEquivalentTo(paradigmLSRs[i])) { return true; } } return false; } U_NAMESPACE_END