diff options
Diffstat (limited to 'deps/node/deps/icu-small/source/common/unormcmp.cpp')
-rw-r--r-- | deps/node/deps/icu-small/source/common/unormcmp.cpp | 640 |
1 files changed, 0 insertions, 640 deletions
diff --git a/deps/node/deps/icu-small/source/common/unormcmp.cpp b/deps/node/deps/icu-small/source/common/unormcmp.cpp deleted file mode 100644 index 689b0b53..00000000 --- a/deps/node/deps/icu-small/source/common/unormcmp.cpp +++ /dev/null @@ -1,640 +0,0 @@ -// © 2016 and later: Unicode, Inc. and others. -// License & terms of use: http://www.unicode.org/copyright.html -/* -******************************************************************************* -* -* Copyright (C) 2001-2014, International Business Machines -* Corporation and others. All Rights Reserved. -* -******************************************************************************* -* file name: unormcmp.cpp -* encoding: UTF-8 -* tab size: 8 (not used) -* indentation:4 -* -* created on: 2004sep13 -* created by: Markus W. Scherer -* -* unorm_compare() function moved here from unorm.cpp for better modularization. -* Depends on both normalization and case folding. -* Allows unorm.cpp to not depend on any character properties code. -*/ - -#include "unicode/utypes.h" - -#if !UCONFIG_NO_NORMALIZATION - -#include "unicode/unorm.h" -#include "unicode/ustring.h" -#include "cmemory.h" -#include "normalizer2impl.h" -#include "ucase.h" -#include "uprops.h" -#include "ustr_imp.h" - -U_NAMESPACE_USE - -/* compare canonically equivalent ------------------------------------------- */ - -/* - * Compare two strings for canonical equivalence. - * Further options include case-insensitive comparison and - * code point order (as opposed to code unit order). - * - * In this function, canonical equivalence is optional as well. - * If canonical equivalence is tested, then both strings must fulfill - * the FCD check. - * - * Semantically, this is equivalent to - * strcmp[CodePointOrder](NFD(foldCase(s1)), NFD(foldCase(s2))) - * where code point order, NFD and foldCase are all optional. - * - * String comparisons almost always yield results before processing both strings - * completely. - * They are generally more efficient working incrementally instead of - * performing the sub-processing (strlen, normalization, case-folding) - * on the entire strings first. - * - * It is also unnecessary to not normalize identical characters. - * - * This function works in principle as follows: - * - * loop { - * get one code unit c1 from s1 (-1 if end of source) - * get one code unit c2 from s2 (-1 if end of source) - * - * if(either string finished) { - * return result; - * } - * if(c1==c2) { - * continue; - * } - * - * // c1!=c2 - * try to decompose/case-fold c1/c2, and continue if one does; - * - * // still c1!=c2 and neither decomposes/case-folds, return result - * return c1-c2; - * } - * - * When a character decomposes, then the pointer for that source changes to - * the decomposition, pushing the previous pointer onto a stack. - * When the end of the decomposition is reached, then the code unit reader - * pops the previous source from the stack. - * (Same for case-folding.) - * - * This is complicated further by operating on variable-width UTF-16. - * The top part of the loop works on code units, while lookups for decomposition - * and case-folding need code points. - * Code points are assembled after the equality/end-of-source part. - * The source pointer is only advanced beyond all code units when the code point - * actually decomposes/case-folds. - * - * If we were on a trail surrogate unit when assembling a code point, - * and the code point decomposes/case-folds, then the decomposition/folding - * result must be compared with the part of the other string that corresponds to - * this string's lead surrogate. - * Since we only assemble a code point when hitting a trail unit when the - * preceding lead units were identical, we back up the other string by one unit - * in such a case. - * - * The optional code point order comparison at the end works with - * the same fix-up as the other code point order comparison functions. - * See ustring.c and the comment near the end of this function. - * - * Assumption: A decomposition or case-folding result string never contains - * a single surrogate. This is a safe assumption in the Unicode Standard. - * Therefore, we do not need to check for surrogate pairs across - * decomposition/case-folding boundaries. - * - * Further assumptions (see verifications tstnorm.cpp): - * The API function checks for FCD first, while the core function - * first case-folds and then decomposes. This requires that case-folding does not - * un-FCD any strings. - * - * The API function may also NFD the input and turn off decomposition. - * This requires that case-folding does not un-NFD strings either. - * - * TODO If any of the above two assumptions is violated, - * then this entire code must be re-thought. - * If this happens, then a simple solution is to case-fold both strings up front - * and to turn off UNORM_INPUT_IS_FCD. - * We already do this when not both strings are in FCD because makeFCD - * would be a partial NFD before the case folding, which does not work. - * Note that all of this is only a problem when case-folding _and_ - * canonical equivalence come together. - * (Comments in unorm_compare() are more up to date than this TODO.) - */ - -/* stack element for previous-level source/decomposition pointers */ -struct CmpEquivLevel { - const UChar *start, *s, *limit; -}; -typedef struct CmpEquivLevel CmpEquivLevel; - -/** - * Internal option for unorm_cmpEquivFold() for decomposing. - * If not set, just do strcasecmp(). - */ -#define _COMPARE_EQUIV 0x80000 - -/* internal function */ -static int32_t -unorm_cmpEquivFold(const UChar *s1, int32_t length1, - const UChar *s2, int32_t length2, - uint32_t options, - UErrorCode *pErrorCode) { - const Normalizer2Impl *nfcImpl; - - /* current-level start/limit - s1/s2 as current */ - const UChar *start1, *start2, *limit1, *limit2; - - /* decomposition and case folding variables */ - const UChar *p; - int32_t length; - - /* stacks of previous-level start/current/limit */ - CmpEquivLevel stack1[2], stack2[2]; - - /* buffers for algorithmic decompositions */ - UChar decomp1[4], decomp2[4]; - - /* case folding buffers, only use current-level start/limit */ - UChar fold1[UCASE_MAX_STRING_LENGTH+1], fold2[UCASE_MAX_STRING_LENGTH+1]; - - /* track which is the current level per string */ - int32_t level1, level2; - - /* current code units, and code points for lookups */ - UChar32 c1, c2, cp1, cp2; - - /* no argument error checking because this itself is not an API */ - - /* - * assume that at least one of the options _COMPARE_EQUIV and U_COMPARE_IGNORE_CASE is set - * otherwise this function must behave exactly as uprv_strCompare() - * not checking for that here makes testing this function easier - */ - - /* normalization/properties data loaded? */ - if((options&_COMPARE_EQUIV)!=0) { - nfcImpl=Normalizer2Factory::getNFCImpl(*pErrorCode); - } else { - nfcImpl=NULL; - } - if(U_FAILURE(*pErrorCode)) { - return 0; - } - - /* initialize */ - start1=s1; - if(length1==-1) { - limit1=NULL; - } else { - limit1=s1+length1; - } - - start2=s2; - if(length2==-1) { - limit2=NULL; - } else { - limit2=s2+length2; - } - - level1=level2=0; - c1=c2=-1; - - /* comparison loop */ - for(;;) { - /* - * here a code unit value of -1 means "get another code unit" - * below it will mean "this source is finished" - */ - - if(c1<0) { - /* get next code unit from string 1, post-increment */ - for(;;) { - if(s1==limit1 || ((c1=*s1)==0 && (limit1==NULL || (options&_STRNCMP_STYLE)))) { - if(level1==0) { - c1=-1; - break; - } - } else { - ++s1; - break; - } - - /* reached end of level buffer, pop one level */ - do { - --level1; - start1=stack1[level1].start; /*Not uninitialized*/ - } while(start1==NULL); - s1=stack1[level1].s; /*Not uninitialized*/ - limit1=stack1[level1].limit; /*Not uninitialized*/ - } - } - - if(c2<0) { - /* get next code unit from string 2, post-increment */ - for(;;) { - if(s2==limit2 || ((c2=*s2)==0 && (limit2==NULL || (options&_STRNCMP_STYLE)))) { - if(level2==0) { - c2=-1; - break; - } - } else { - ++s2; - break; - } - - /* reached end of level buffer, pop one level */ - do { - --level2; - start2=stack2[level2].start; /*Not uninitialized*/ - } while(start2==NULL); - s2=stack2[level2].s; /*Not uninitialized*/ - limit2=stack2[level2].limit; /*Not uninitialized*/ - } - } - - /* - * compare c1 and c2 - * either variable c1, c2 is -1 only if the corresponding string is finished - */ - if(c1==c2) { - if(c1<0) { - return 0; /* c1==c2==-1 indicating end of strings */ - } - c1=c2=-1; /* make us fetch new code units */ - continue; - } else if(c1<0) { - return -1; /* string 1 ends before string 2 */ - } else if(c2<0) { - return 1; /* string 2 ends before string 1 */ - } - /* c1!=c2 && c1>=0 && c2>=0 */ - - /* get complete code points for c1, c2 for lookups if either is a surrogate */ - cp1=c1; - if(U_IS_SURROGATE(c1)) { - UChar c; - - if(U_IS_SURROGATE_LEAD(c1)) { - if(s1!=limit1 && U16_IS_TRAIL(c=*s1)) { - /* advance ++s1; only below if cp1 decomposes/case-folds */ - cp1=U16_GET_SUPPLEMENTARY(c1, c); - } - } else /* isTrail(c1) */ { - if(start1<=(s1-2) && U16_IS_LEAD(c=*(s1-2))) { - cp1=U16_GET_SUPPLEMENTARY(c, c1); - } - } - } - - cp2=c2; - if(U_IS_SURROGATE(c2)) { - UChar c; - - if(U_IS_SURROGATE_LEAD(c2)) { - if(s2!=limit2 && U16_IS_TRAIL(c=*s2)) { - /* advance ++s2; only below if cp2 decomposes/case-folds */ - cp2=U16_GET_SUPPLEMENTARY(c2, c); - } - } else /* isTrail(c2) */ { - if(start2<=(s2-2) && U16_IS_LEAD(c=*(s2-2))) { - cp2=U16_GET_SUPPLEMENTARY(c, c2); - } - } - } - - /* - * go down one level for each string - * continue with the main loop as soon as there is a real change - */ - - if( level1==0 && (options&U_COMPARE_IGNORE_CASE) && - (length=ucase_toFullFolding((UChar32)cp1, &p, options))>=0 - ) { - /* cp1 case-folds to the code point "length" or to p[length] */ - if(U_IS_SURROGATE(c1)) { - if(U_IS_SURROGATE_LEAD(c1)) { - /* advance beyond source surrogate pair if it case-folds */ - ++s1; - } else /* isTrail(c1) */ { - /* - * we got a supplementary code point when hitting its trail surrogate, - * therefore the lead surrogate must have been the same as in the other string; - * compare this decomposition with the lead surrogate in the other string - * remember that this simulates bulk text replacement: - * the decomposition would replace the entire code point - */ - --s2; - c2=*(s2-1); - } - } - - /* push current level pointers */ - stack1[0].start=start1; - stack1[0].s=s1; - stack1[0].limit=limit1; - ++level1; - - /* copy the folding result to fold1[] */ - if(length<=UCASE_MAX_STRING_LENGTH) { - u_memcpy(fold1, p, length); - } else { - int32_t i=0; - U16_APPEND_UNSAFE(fold1, i, length); - length=i; - } - - /* set next level pointers to case folding */ - start1=s1=fold1; - limit1=fold1+length; - - /* get ready to read from decomposition, continue with loop */ - c1=-1; - continue; - } - - if( level2==0 && (options&U_COMPARE_IGNORE_CASE) && - (length=ucase_toFullFolding((UChar32)cp2, &p, options))>=0 - ) { - /* cp2 case-folds to the code point "length" or to p[length] */ - if(U_IS_SURROGATE(c2)) { - if(U_IS_SURROGATE_LEAD(c2)) { - /* advance beyond source surrogate pair if it case-folds */ - ++s2; - } else /* isTrail(c2) */ { - /* - * we got a supplementary code point when hitting its trail surrogate, - * therefore the lead surrogate must have been the same as in the other string; - * compare this decomposition with the lead surrogate in the other string - * remember that this simulates bulk text replacement: - * the decomposition would replace the entire code point - */ - --s1; - c1=*(s1-1); - } - } - - /* push current level pointers */ - stack2[0].start=start2; - stack2[0].s=s2; - stack2[0].limit=limit2; - ++level2; - - /* copy the folding result to fold2[] */ - if(length<=UCASE_MAX_STRING_LENGTH) { - u_memcpy(fold2, p, length); - } else { - int32_t i=0; - U16_APPEND_UNSAFE(fold2, i, length); - length=i; - } - - /* set next level pointers to case folding */ - start2=s2=fold2; - limit2=fold2+length; - - /* get ready to read from decomposition, continue with loop */ - c2=-1; - continue; - } - - if( level1<2 && (options&_COMPARE_EQUIV) && - 0!=(p=nfcImpl->getDecomposition((UChar32)cp1, decomp1, length)) - ) { - /* cp1 decomposes into p[length] */ - if(U_IS_SURROGATE(c1)) { - if(U_IS_SURROGATE_LEAD(c1)) { - /* advance beyond source surrogate pair if it decomposes */ - ++s1; - } else /* isTrail(c1) */ { - /* - * we got a supplementary code point when hitting its trail surrogate, - * therefore the lead surrogate must have been the same as in the other string; - * compare this decomposition with the lead surrogate in the other string - * remember that this simulates bulk text replacement: - * the decomposition would replace the entire code point - */ - --s2; - c2=*(s2-1); - } - } - - /* push current level pointers */ - stack1[level1].start=start1; - stack1[level1].s=s1; - stack1[level1].limit=limit1; - ++level1; - - /* set empty intermediate level if skipped */ - if(level1<2) { - stack1[level1++].start=NULL; - } - - /* set next level pointers to decomposition */ - start1=s1=p; - limit1=p+length; - - /* get ready to read from decomposition, continue with loop */ - c1=-1; - continue; - } - - if( level2<2 && (options&_COMPARE_EQUIV) && - 0!=(p=nfcImpl->getDecomposition((UChar32)cp2, decomp2, length)) - ) { - /* cp2 decomposes into p[length] */ - if(U_IS_SURROGATE(c2)) { - if(U_IS_SURROGATE_LEAD(c2)) { - /* advance beyond source surrogate pair if it decomposes */ - ++s2; - } else /* isTrail(c2) */ { - /* - * we got a supplementary code point when hitting its trail surrogate, - * therefore the lead surrogate must have been the same as in the other string; - * compare this decomposition with the lead surrogate in the other string - * remember that this simulates bulk text replacement: - * the decomposition would replace the entire code point - */ - --s1; - c1=*(s1-1); - } - } - - /* push current level pointers */ - stack2[level2].start=start2; - stack2[level2].s=s2; - stack2[level2].limit=limit2; - ++level2; - - /* set empty intermediate level if skipped */ - if(level2<2) { - stack2[level2++].start=NULL; - } - - /* set next level pointers to decomposition */ - start2=s2=p; - limit2=p+length; - - /* get ready to read from decomposition, continue with loop */ - c2=-1; - continue; - } - - /* - * no decomposition/case folding, max level for both sides: - * return difference result - * - * code point order comparison must not just return cp1-cp2 - * because when single surrogates are present then the surrogate pairs - * that formed cp1 and cp2 may be from different string indexes - * - * example: { d800 d800 dc01 } vs. { d800 dc00 }, compare at second code units - * c1=d800 cp1=10001 c2=dc00 cp2=10000 - * cp1-cp2>0 but c1-c2<0 and in fact in UTF-32 it is { d800 10001 } < { 10000 } - * - * therefore, use same fix-up as in ustring.c/uprv_strCompare() - * except: uprv_strCompare() fetches c=*s while this functions fetches c=*s++ - * so we have slightly different pointer/start/limit comparisons here - */ - - if(c1>=0xd800 && c2>=0xd800 && (options&U_COMPARE_CODE_POINT_ORDER)) { - /* subtract 0x2800 from BMP code points to make them smaller than supplementary ones */ - if( - (c1<=0xdbff && s1!=limit1 && U16_IS_TRAIL(*s1)) || - (U16_IS_TRAIL(c1) && start1!=(s1-1) && U16_IS_LEAD(*(s1-2))) - ) { - /* part of a surrogate pair, leave >=d800 */ - } else { - /* BMP code point - may be surrogate code point - make <d800 */ - c1-=0x2800; - } - - if( - (c2<=0xdbff && s2!=limit2 && U16_IS_TRAIL(*s2)) || - (U16_IS_TRAIL(c2) && start2!=(s2-1) && U16_IS_LEAD(*(s2-2))) - ) { - /* part of a surrogate pair, leave >=d800 */ - } else { - /* BMP code point - may be surrogate code point - make <d800 */ - c2-=0x2800; - } - } - - return c1-c2; - } -} - -static -UBool _normalize(const Normalizer2 *n2, const UChar *s, int32_t length, - UnicodeString &normalized, UErrorCode *pErrorCode) { - UnicodeString str(length<0, s, length); - - // check if s fulfill the conditions - int32_t spanQCYes=n2->spanQuickCheckYes(str, *pErrorCode); - if (U_FAILURE(*pErrorCode)) { - return FALSE; - } - /* - * ICU 2.4 had a further optimization: - * If both strings were not in FCD, then they were both NFD'ed, - * and the _COMPARE_EQUIV option was turned off. - * It is not entirely clear that this is valid with the current - * definition of the canonical caseless match. - * Therefore, ICU 2.6 removes that optimization. - */ - if(spanQCYes<str.length()) { - UnicodeString unnormalized=str.tempSubString(spanQCYes); - normalized.setTo(FALSE, str.getBuffer(), spanQCYes); - n2->normalizeSecondAndAppend(normalized, unnormalized, *pErrorCode); - if (U_SUCCESS(*pErrorCode)) { - return TRUE; - } - } - return FALSE; -} - -U_CAPI int32_t U_EXPORT2 -unorm_compare(const UChar *s1, int32_t length1, - const UChar *s2, int32_t length2, - uint32_t options, - UErrorCode *pErrorCode) { - /* argument checking */ - if(U_FAILURE(*pErrorCode)) { - return 0; - } - if(s1==0 || length1<-1 || s2==0 || length2<-1) { - *pErrorCode=U_ILLEGAL_ARGUMENT_ERROR; - return 0; - } - - UnicodeString fcd1, fcd2; - int32_t normOptions=(int32_t)(options>>UNORM_COMPARE_NORM_OPTIONS_SHIFT); - options|=_COMPARE_EQUIV; - - /* - * UAX #21 Case Mappings, as fixed for Unicode version 4 - * (see Jitterbug 2021), defines a canonical caseless match as - * - * A string X is a canonical caseless match - * for a string Y if and only if - * NFD(toCasefold(NFD(X))) = NFD(toCasefold(NFD(Y))) - * - * For better performance, we check for FCD (or let the caller tell us that - * both strings are in FCD) for the inner normalization. - * BasicNormalizerTest::FindFoldFCDExceptions() makes sure that - * case-folding preserves the FCD-ness of a string. - * The outer normalization is then only performed by unorm_cmpEquivFold() - * when there is a difference. - * - * Exception: When using the Turkic case-folding option, we do perform - * full NFD first. This is because in the Turkic case precomposed characters - * with 0049 capital I or 0069 small i fold differently whether they - * are first decomposed or not, so an FCD check - a check only for - * canonical order - is not sufficient. - */ - if(!(options&UNORM_INPUT_IS_FCD) || (options&U_FOLD_CASE_EXCLUDE_SPECIAL_I)) { - const Normalizer2 *n2; - if(options&U_FOLD_CASE_EXCLUDE_SPECIAL_I) { - n2=Normalizer2::getNFDInstance(*pErrorCode); - } else { - n2=Normalizer2Factory::getFCDInstance(*pErrorCode); - } - if (U_FAILURE(*pErrorCode)) { - return 0; - } - - if(normOptions&UNORM_UNICODE_3_2) { - const UnicodeSet *uni32=uniset_getUnicode32Instance(*pErrorCode); - FilteredNormalizer2 fn2(*n2, *uni32); - if(_normalize(&fn2, s1, length1, fcd1, pErrorCode)) { - s1=fcd1.getBuffer(); - length1=fcd1.length(); - } - if(_normalize(&fn2, s2, length2, fcd2, pErrorCode)) { - s2=fcd2.getBuffer(); - length2=fcd2.length(); - } - } else { - if(_normalize(n2, s1, length1, fcd1, pErrorCode)) { - s1=fcd1.getBuffer(); - length1=fcd1.length(); - } - if(_normalize(n2, s2, length2, fcd2, pErrorCode)) { - s2=fcd2.getBuffer(); - length2=fcd2.length(); - } - } - } - - if(U_SUCCESS(*pErrorCode)) { - return unorm_cmpEquivFold(s1, length1, s2, length2, options, pErrorCode); - } else { - return 0; - } -} - -#endif /* #if !UCONFIG_NO_NORMALIZATION */ |