| // © 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 = U_INITONCE_INITIALIZER; | |
| 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 |