../deps/icu-small/source/i18n/collationbuilder.h

Bug Summary

File:	out/../deps/icu-small/source/i18n/collationbuilder.h
Warning:	line 253, column 21 The result of the left shift is undefined due to shifting '2147483647' by '8', which is unrepresentable in the unsigned version of the return type 'int32_t'

Annotated Source Code

Press '?' to see keyboard shortcuts

Show analyzer invocation

clang -cc1 -cc1 -triple x86_64-unknown-linux-gnu -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name collationbuilder.cpp -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=cplusplus -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -mrelocation-model pic -pic-level 2 -pic-is-pie -mframe-pointer=all -fmath-errno -ffp-contract=on -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fcoverage-compilation-dir=/home/maurizio/node-v18.6.0/out -resource-dir /usr/local/lib/clang/16.0.0 -D V8_DEPRECATION_WARNINGS -D V8_IMMINENT_DEPRECATION_WARNINGS -D _GLIBCXX_USE_CXX11_ABI=1 -D NODE_OPENSSL_CONF_NAME=nodejs_conf -D NODE_OPENSSL_HAS_QUIC -D __STDC_FORMAT_MACROS -D OPENSSL_NO_PINSHARED -D OPENSSL_THREADS -D U_COMMON_IMPLEMENTATION=1 -D U_I18N_IMPLEMENTATION=1 -D U_IO_IMPLEMENTATION=1 -D U_TOOLUTIL_IMPLEMENTATION=1 -D U_ATTRIBUTE_DEPRECATED= -D _CRT_SECURE_NO_DEPRECATE= -D U_STATIC_IMPLEMENTATION=1 -D UCONFIG_NO_SERVICE=1 -D U_ENABLE_DYLOAD=0 -D U_HAVE_STD_STRING=1 -D UCONFIG_NO_BREAK_ITERATION=0 -I ../deps/icu-small/source/common -I ../deps/icu-small/source/i18n -I ../deps/icu-small/source/tools/toolutil -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8 -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/x86_64-redhat-linux -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../include/c++/8/backward -internal-isystem /usr/local/lib/clang/16.0.0/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-redhat-linux/8/../../../../x86_64-redhat-linux/include -internal-externc-isystem /include -internal-externc-isystem /usr/include -O3 -Wno-unused-parameter -Wno-deprecated-declarations -Wno-strict-aliasing -std=gnu++17 -fdeprecated-macro -fdebug-compilation-dir=/home/maurizio/node-v18.6.0/out -ferror-limit 19 -fgnuc-version=4.2.1 -vectorize-loops -vectorize-slp -analyzer-output=html -faddrsig -D__GCC_HAVE_DWARF2_CFI_ASM=1 -o /tmp/scan-build-2022-08-22-142216-507842-1 -x c++ ../deps/icu-small/source/i18n/collationbuilder.cpp

../deps/icu-small/source/i18n/collationbuilder.cpp

→

1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2013-2014, International Business Machines
6* Corporation and others.  All Rights Reserved.
7*******************************************************************************
8* collationbuilder.cpp
9*
10* (replaced the former ucol_bld.cpp)
11*
12* created on: 2013may06
13* created by: Markus W. Scherer
14*/

16#ifdef DEBUG_COLLATION_BUILDER
17#include <stdio.h>
18#endif

20#include "unicode/utypes.h"

22#if !UCONFIG_NO_COLLATION0

24#include "unicode/caniter.h"
25#include "unicode/normalizer2.h"
26#include "unicode/tblcoll.h"
27#include "unicode/parseerr.h"
28#include "unicode/uchar.h"
29#include "unicode/ucol.h"
30#include "unicode/unistr.h"
31#include "unicode/usetiter.h"
32#include "unicode/utf16.h"
33#include "unicode/uversion.h"
34#include "cmemory.h"
35#include "collation.h"
36#include "collationbuilder.h"
37#include "collationdata.h"
38#include "collationdatabuilder.h"
39#include "collationfastlatin.h"
40#include "collationroot.h"
41#include "collationrootelements.h"
42#include "collationruleparser.h"
43#include "collationsettings.h"
44#include "collationtailoring.h"
45#include "collationweights.h"
46#include "normalizer2impl.h"
47#include "uassert.h"
48#include "ucol_imp.h"
49#include "utf16collationiterator.h"

51U_NAMESPACE_BEGINnamespace icu_71 {

53namespace {

55class BundleImporter : public CollationRuleParser::Importer {
56public:
  BundleImporter() {}
  virtual ~BundleImporter();
  virtual void getRules(
          const char *localeID, const char *collationType,
          UnicodeString &rules,
          const char *&errorReason, UErrorCode &errorCode) override;
63};

65BundleImporter::~BundleImporter() {}

67void
68BundleImporter::getRules(
      const char *localeID, const char *collationType,
      UnicodeString &rules,
      const char *& /*errorReason*/, UErrorCode &errorCode) {
  CollationLoader::loadRules(localeID, collationType, rules, errorCode);
73}

75}  // namespace

77// RuleBasedCollator implementation ---------------------------------------- ***

79// These methods are here, rather than in rulebasedcollator.cpp,
80// for modularization:
81// Most code using Collator does not need to build a Collator from rules.
82// By moving these constructors and helper methods to a separate file,
83// most code will not have a static dependency on the builder code.

85RuleBasedCollator::RuleBasedCollator()
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
93}

95RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, UErrorCode &errorCode)
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
  internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, NULL__null, NULL__null, errorCode);
104}

106RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules, ECollationStrength strength,
                                   UErrorCode &errorCode)
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
  internalBuildTailoring(rules, strength, UCOL_DEFAULT, NULL__null, NULL__null, errorCode);
116}

118RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
                                   UColAttributeValue decompositionMode,
                                   UErrorCode &errorCode)
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
  internalBuildTailoring(rules, UCOL_DEFAULT, decompositionMode, NULL__null, NULL__null, errorCode);
129}

131RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
                                   ECollationStrength strength,
                                   UColAttributeValue decompositionMode,
                                   UErrorCode &errorCode)
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
  internalBuildTailoring(rules, strength, decompositionMode, NULL__null, NULL__null, errorCode);
143}

145RuleBasedCollator::RuleBasedCollator(const UnicodeString &rules,
                                   UParseError &parseError, UnicodeString &reason,
                                   UErrorCode &errorCode)
      : data(NULL__null),
        settings(NULL__null),
        tailoring(NULL__null),
        cacheEntry(NULL__null),
        validLocale(""),
        explicitlySetAttributes(0),
        actualLocaleIsSameAsValid(FALSE0) {
  internalBuildTailoring(rules, UCOL_DEFAULT, UCOL_DEFAULT, &parseError, &reason, errorCode);
156}

158void
159RuleBasedCollator::internalBuildTailoring(const UnicodeString &rules,
                                        int32_t strength,
                                        UColAttributeValue decompositionMode,
                                        UParseError *outParseError, UnicodeString *outReason,
                                        UErrorCode &errorCode) {
  const CollationTailoring *base = CollationRoot::getRoot(errorCode);
  if(U_FAILURE(errorCode)) { return; }
  if(outReason != NULL__null) { outReason->remove(); }
  CollationBuilder builder(base, errorCode);
  UVersionInfo noVersion = { 0, 0, 0, 0 };
  BundleImporter importer;
  LocalPointer<CollationTailoring> t(builder.parseAndBuild(rules, noVersion,
                                                           &importer,
                                                           outParseError, errorCode));
  if(U_FAILURE(errorCode)) {
      const char *reason = builder.getErrorReason();
      if(reason != NULL__null && outReason != NULL__null) {
          *outReason = UnicodeString(reason, -1, US_INVicu::UnicodeString::kInvariant);
      }
      return;
  }
  t->actualLocale.setToBogus();
  adoptTailoring(t.orphan(), errorCode);
  // Set attributes after building the collator,
  // to keep the default settings consistent with the rule string.
  if(strength != UCOL_DEFAULT) {
      setAttribute(UCOL_STRENGTH, (UColAttributeValue)strength, errorCode);
  }
  if(decompositionMode != UCOL_DEFAULT) {
      setAttribute(UCOL_NORMALIZATION_MODE, decompositionMode, errorCode);
  }
190}

192// CollationBuilder implementation ----------------------------------------- ***

194// Some compilers don't care if constants are defined in the .cpp file.
195// MS Visual C++ does not like it, but gcc requires it. clang does not care.
196#ifndef _MSC_VER
197const int32_t CollationBuilder::HAS_BEFORE2;
198const int32_t CollationBuilder::HAS_BEFORE3;
199#endif

201CollationBuilder::CollationBuilder(const CollationTailoring *b, UErrorCode &errorCode)
      : nfd(*Normalizer2::getNFDInstance(errorCode)),
        fcd(*Normalizer2Factory::getFCDInstance(errorCode)),
        nfcImpl(*Normalizer2Factory::getNFCImpl(errorCode)),
        base(b),
        baseData(b->data),
        rootElements(b->data->rootElements, b->data->rootElementsLength),
        variableTop(0),
        dataBuilder(new CollationDataBuilder(errorCode)), fastLatinEnabled(TRUE1),
        errorReason(NULL__null),
        cesLength(0),
        rootPrimaryIndexes(errorCode), nodes(errorCode) {
  nfcImpl.ensureCanonIterData(errorCode);
  if(U_FAILURE(errorCode)) {
      errorReason = "CollationBuilder fields initialization failed";
      return;
  }
  if(dataBuilder == NULL__null) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return;
  }
  dataBuilder->initForTailoring(baseData, errorCode);
  if(U_FAILURE(errorCode)) {
      errorReason = "CollationBuilder initialization failed";
  }
226}

228CollationBuilder::~CollationBuilder() {
  delete dataBuilder;
230}

232CollationTailoring *
233CollationBuilder::parseAndBuild(const UnicodeString &ruleString,
                              const UVersionInfo rulesVersion,
                              CollationRuleParser::Importer *importer,
                              UParseError *outParseError,
                              UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return NULL__null; }
  if(baseData->rootElements == NULL__null) {
      errorCode = U_MISSING_RESOURCE_ERROR;
      errorReason = "missing root elements data, tailoring not supported";
      return NULL__null;
  }
  LocalPointer<CollationTailoring> tailoring(new CollationTailoring(base->settings));
  if(tailoring.isNull() || tailoring->isBogus()) {
      errorCode = U_MEMORY_ALLOCATION_ERROR;
      return NULL__null;
  }
  CollationRuleParser parser(baseData, errorCode);
  if(U_FAILURE(errorCode)) { return NULL__null; }
  // Note: This always bases &[last variable] and &[first regular]
  // on the root collator's maxVariable/variableTop.
  // If we wanted this to change after [maxVariable x], then we would keep
  // the tailoring.settings pointer here and read its variableTop when we need it.
  // See http://unicode.org/cldr/trac/ticket/6070
  variableTop = base->settings->variableTop;
  parser.setSink(this);
  parser.setImporter(importer);
  CollationSettings &ownedSettings = *SharedObject::copyOnWrite(tailoring->settings);
  parser.parse(ruleString, ownedSettings, outParseError, errorCode);
  errorReason = parser.getErrorReason();
  if(U_FAILURE(errorCode)) { return NULL__null; }
  if(dataBuilder->hasMappings()) {
      makeTailoredCEs(errorCode);
      closeOverComposites(errorCode);
      finalizeCEs(errorCode);
      // Copy all of ASCII, and Latin-1 letters, into each tailoring.
      optimizeSet.add(0, 0x7f);
      optimizeSet.add(0xc0, 0xff);
      // Hangul is decomposed on the fly during collation,
      // and the tailoring data is always built with HANGUL_TAG specials.
      optimizeSet.remove(Hangul::HANGUL_BASE, Hangul::HANGUL_END);
      dataBuilder->optimize(optimizeSet, errorCode);
      tailoring->ensureOwnedData(errorCode);
      if(U_FAILURE(errorCode)) { return NULL__null; }
      if(fastLatinEnabled) { dataBuilder->enableFastLatin(); }
      dataBuilder->build(*tailoring->ownedData, errorCode);
      tailoring->builder = dataBuilder;
      dataBuilder = NULL__null;
  } else {
      tailoring->data = baseData;
  }
  if(U_FAILURE(errorCode)) { return NULL__null; }
  ownedSettings.fastLatinOptions = CollationFastLatin::getOptions(
      tailoring->data, ownedSettings,
      ownedSettings.fastLatinPrimaries, UPRV_LENGTHOF(ownedSettings.fastLatinPrimaries)(int32_t)(sizeof(ownedSettings.fastLatinPrimaries)/sizeof((ownedSettings
.fastLatinPrimaries)[0])));
  tailoring->rules = ruleString;
  tailoring->rules.getTerminatedBuffer();  // ensure NUL-termination
  tailoring->setVersion(base->version, rulesVersion);
  return tailoring.orphan();
291}

293void
294CollationBuilder::addReset(int32_t strength, const UnicodeString &str,
                         const char *&parserErrorReason, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
1
Taking false branch→
  U_ASSERT(!str.isEmpty())(void)0;
  if(str.charAt(0) == CollationRuleParser::POS_LEAD) {
2
←
Taking false branch→
      ces[0] = getSpecialResetPosition(str, parserErrorReason, errorCode);
      cesLength = 1;
      if(U_FAILURE(errorCode)) { return; }
      U_ASSERT((ces[0] & Collation::CASE_AND_QUATERNARY_MASK) == 0)(void)0;
  } else {
      // normal reset to a character or string
      UnicodeString nfdString = nfd.normalize(str, errorCode);
      if(U_FAILURE(errorCode)) {
3
←
Taking false branch→
          parserErrorReason = "normalizing the reset position";
          return;
      }
      cesLength = dataBuilder->getCEs(nfdString, ces, 0);
      if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
4
←
Assuming 'MAX_EXPANSION_LENGTH' is >= field 'cesLength'→
5
←
Taking false branch→
          errorCode = U_ILLEGAL_ARGUMENT_ERROR;
          parserErrorReason = "reset position maps to too many collation elements (more than 31)";
          return;
      }
  }
  if(strength == UCOL_IDENTICAL) { return; }  // simple reset-at-position
6
←
Assuming 'strength' is not equal to UCOL_IDENTICAL→
7
←
Taking false branch→

  // &[before strength]position
  U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_TERTIARY)(void)0;
  int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);
8
←
Calling 'CollationBuilder::findOrInsertNodeForCEs'→
29
←
Returning from 'CollationBuilder::findOrInsertNodeForCEs'→
  if(U_FAILURE(errorCode)) { return; }
30
←
Taking false branch→

  int64_t node = nodes.elementAti(index);
  // If the index is for a "weaker" node,
  // then skip backwards over this and further "weaker" nodes.
  while(strengthFromNode(node) > strength) {
31
←
Assuming the condition is false→
      index = previousIndexFromNode(node);
      node = nodes.elementAti(index);
  }

  // Find or insert a node whose index we will put into a temporary CE.
  if(strengthFromNode(node) == strength && isTailoredNode(node)) {
32
←
Assuming the condition is false→
      // Reset to just before this same-strength tailored node.
      index = previousIndexFromNode(node);
  } else if(strength == UCOL_PRIMARY) {
33
←
Assuming 'strength' is not equal to UCOL_PRIMARY→
34
←
Taking false branch→
      // root primary node (has no previous index)
      uint32_t p = weight32FromNode(node);
      if(p == 0) {
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "reset primary-before ignorable not possible";
          return;
      }
      if(p <= rootElements.getFirstPrimary()) {
          // There is no primary gap between ignorables and the space-first-primary.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "reset primary-before first non-ignorable not supported";
          return;
      }
      if(p == Collation::FIRST_TRAILING_PRIMARY) {
          // We do not support tailoring to an unassigned-implicit CE.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "reset primary-before [first trailing] not supported";
          return;
      }
      p = rootElements.getPrimaryBefore(p, baseData->isCompressiblePrimary(p));
      index = findOrInsertNodeForPrimary(p, errorCode);
      // Go to the last node in this list:
      // Tailor after the last node between adjacent root nodes.
      for(;;) {
          node = nodes.elementAti(index);
          int32_t nextIndex = nextIndexFromNode(node);
          if(nextIndex == 0) { break; }
          index = nextIndex;
      }
  } else {
      // &[before 2] or &[before 3]
      index = findCommonNode(index, UCOL_SECONDARY);
      if(strength34.1
'strength' is < UCOL_TERTIARY
1
'strength' is < UCOL_TERTIARY
 >= UCOL_TERTIARY) {
35
←
Taking false branch→
          index = findCommonNode(index, UCOL_TERTIARY);
      }
      // findCommonNode() stayed on the stronger node or moved to
      // an explicit common-weight node of the reset-before strength.
      node = nodes.elementAti(index);
      if(strengthFromNode(node) == strength) {
36
←
Assuming the condition is true→
37
←
Taking true branch→
          // Found a same-strength node with an explicit weight.
          uint32_t weight16 = weight16FromNode(node);
          if(weight16 == 0) {
38
←
Assuming 'weight16' is not equal to 0→
39
←
Taking false branch→
              errorCode = U_UNSUPPORTED_ERROR;
              if(strength == UCOL_SECONDARY) {
                  parserErrorReason = "reset secondary-before secondary ignorable not possible";
              } else {
                  parserErrorReason = "reset tertiary-before completely ignorable not possible";
              }
              return;
          }
          U_ASSERT(weight16 > Collation::BEFORE_WEIGHT16)(void)0;
          // Reset to just before this node.
          // Insert the preceding same-level explicit weight if it is not there already.
          // Which explicit weight immediately precedes this one?
          weight16 = getWeight16Before(index, node, strength);
          // Does this preceding weight have a node?
          uint32_t previousWeight16;
          int32_t previousIndex = previousIndexFromNode(node);
          for(int32_t i = previousIndex;; i = previousIndexFromNode(node)) {
40
←
Loop condition is true.  Entering loop body→
41
←
Loop condition is true.  Entering loop body→
              node = nodes.elementAti(i);
              int32_t previousStrength = strengthFromNode(node);
              if(previousStrength40.1
'previousStrength' is >= 'strength'
1
'previousStrength' is >= 'strength'
 < strength) {
42
←
Assuming 'previousStrength' is < 'strength'→
43
←
Taking true branch→
                  U_ASSERT(weight16 >= Collation::COMMON_WEIGHT16 || i == previousIndex)(void)0;
                  // Either the reset element has an above-common weight and
                  // the parent node provides the implied common weight,
                  // or the reset element has a weight<=common in the node
                  // right after the parent, and we need to insert the preceding weight.
                  previousWeight16 = Collation::COMMON_WEIGHT16;
                  break;
              } else if(previousStrength40.2
'previousStrength' is not equal to 'strength'
2
'previousStrength' is not equal to 'strength'
 == strength && !isTailoredNode(node)) {
                  previousWeight16 = weight16FromNode(node);
                  break;
              }
              // Skip weaker nodes and same-level tailored nodes.
          }
          if(previousWeight16 == weight16) {
44
←
 Execution continues on line 412→
45
←
Assuming 'previousWeight16' is not equal to 'weight16'→
46
←
Taking false branch→
              // The preceding weight has a node,
              // maybe with following weaker or tailored nodes.
              // Reset to the last of them.
              index = previousIndex;
          } else {
              // Insert a node with the preceding weight, reset to that.
              node = nodeFromWeight16(weight16) | nodeFromStrength(strength);
              index = insertNodeBetween(previousIndex, index, node, errorCode);
47
←
Calling 'CollationBuilder::insertNodeBetween'→
          }
      } else {
          // Found a stronger node with implied strength-common weight.
          uint32_t weight16 = getWeight16Before(index, node, strength);
          index = findOrInsertWeakNode(index, weight16, strength, errorCode);
      }
      // Strength of the temporary CE = strength of its reset position.
      // Code above raises an error if the before-strength is stronger.
      strength = ceStrength(ces[cesLength - 1]);
  }
  if(U_FAILURE(errorCode)) {
      parserErrorReason = "inserting reset position for &[before n]";
      return;
  }
  ces[cesLength - 1] = tempCEFromIndexAndStrength(index, strength);
436}

438uint32_t
439CollationBuilder::getWeight16Before(int32_t index, int64_t node, int32_t level) {
  U_ASSERT(strengthFromNode(node) < level || !isTailoredNode(node))(void)0;
  // Collect the root CE weights if this node is for a root CE.
  // If it is not, then return the low non-primary boundary for a tailored CE.
  uint32_t t;
  if(strengthFromNode(node) == UCOL_TERTIARY) {
      t = weight16FromNode(node);
  } else {
      t = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.
  }
  while(strengthFromNode(node) > UCOL_SECONDARY) {
      index = previousIndexFromNode(node);
      node = nodes.elementAti(index);
  }
  if(isTailoredNode(node)) {
      return Collation::BEFORE_WEIGHT16;
  }
  uint32_t s;
  if(strengthFromNode(node) == UCOL_SECONDARY) {
      s = weight16FromNode(node);
  } else {
      s = Collation::COMMON_WEIGHT16;  // Stronger node with implied common weight.
  }
  while(strengthFromNode(node) > UCOL_PRIMARY) {
      index = previousIndexFromNode(node);
      node = nodes.elementAti(index);
  }
  if(isTailoredNode(node)) {
      return Collation::BEFORE_WEIGHT16;
  }
  // [p, s, t] is a root CE. Return the preceding weight for the requested level.
  uint32_t p = weight32FromNode(node);
  uint32_t weight16;
  if(level == UCOL_SECONDARY) {
      weight16 = rootElements.getSecondaryBefore(p, s);
  } else {
      weight16 = rootElements.getTertiaryBefore(p, s, t);
      U_ASSERT((weight16 & ~Collation::ONLY_TERTIARY_MASK) == 0)(void)0;
  }
  return weight16;
479}

481int64_t
482CollationBuilder::getSpecialResetPosition(const UnicodeString &str,
                                        const char *&parserErrorReason, UErrorCode &errorCode) {
  U_ASSERT(str.length() == 2)(void)0;
  int64_t ce;
  int32_t strength = UCOL_PRIMARY;
  UBool isBoundary = FALSE0;
  UChar32 pos = str.charAt(1) - CollationRuleParser::POS_BASE;
  U_ASSERT(0 <= pos && pos <= CollationRuleParser::LAST_TRAILING)(void)0;
  switch(pos) {
  case CollationRuleParser::FIRST_TERTIARY_IGNORABLE:
      // Quaternary CEs are not supported.
      // Non-zero quaternary weights are possible only on tertiary or stronger CEs.
      return 0;
  case CollationRuleParser::LAST_TERTIARY_IGNORABLE:
      return 0;
  case CollationRuleParser::FIRST_SECONDARY_IGNORABLE: {
      // Look for a tailored tertiary node after [0, 0, 0].
      int32_t index = findOrInsertNodeForRootCE(0, UCOL_TERTIARY, errorCode);
      if(U_FAILURE(errorCode)) { return 0; }
      int64_t node = nodes.elementAti(index);
      if((index = nextIndexFromNode(node)) != 0) {
          node = nodes.elementAti(index);
          U_ASSERT(strengthFromNode(node) <= UCOL_TERTIARY)(void)0;
          if(isTailoredNode(node) && strengthFromNode(node) == UCOL_TERTIARY) {
              return tempCEFromIndexAndStrength(index, UCOL_TERTIARY);
          }
      }
      return rootElements.getFirstTertiaryCE();
      // No need to look for nodeHasAnyBefore() on a tertiary node.
  }
  case CollationRuleParser::LAST_SECONDARY_IGNORABLE:
      ce = rootElements.getLastTertiaryCE();
      strength = UCOL_TERTIARY;
      break;
  case CollationRuleParser::FIRST_PRIMARY_IGNORABLE: {
      // Look for a tailored secondary node after [0, 0, *].
      int32_t index = findOrInsertNodeForRootCE(0, UCOL_SECONDARY, errorCode);
      if(U_FAILURE(errorCode)) { return 0; }
      int64_t node = nodes.elementAti(index);
      while((index = nextIndexFromNode(node)) != 0) {
          node = nodes.elementAti(index);
          strength = strengthFromNode(node);
          if(strength < UCOL_SECONDARY) { break; }
          if(strength == UCOL_SECONDARY) {
              if(isTailoredNode(node)) {
                  if(nodeHasBefore3(node)) {
                      index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
                      U_ASSERT(isTailoredNode(nodes.elementAti(index)))(void)0;
                  }
                  return tempCEFromIndexAndStrength(index, UCOL_SECONDARY);
              } else {
                  break;
              }
          }
      }
      ce = rootElements.getFirstSecondaryCE();
      strength = UCOL_SECONDARY;
      break;
  }
  case CollationRuleParser::LAST_PRIMARY_IGNORABLE:
      ce = rootElements.getLastSecondaryCE();
      strength = UCOL_SECONDARY;
      break;
  case CollationRuleParser::FIRST_VARIABLE:
      ce = rootElements.getFirstPrimaryCE();
      isBoundary = TRUE1;  // FractionalUCA.txt: FDD1 00A0, SPACE first primary
      break;
  case CollationRuleParser::LAST_VARIABLE:
      ce = rootElements.lastCEWithPrimaryBefore(variableTop + 1);
      break;
  case CollationRuleParser::FIRST_REGULAR:
      ce = rootElements.firstCEWithPrimaryAtLeast(variableTop + 1);
      isBoundary = TRUE1;  // FractionalUCA.txt: FDD1 263A, SYMBOL first primary
      break;
  case CollationRuleParser::LAST_REGULAR:
      // Use the Hani-first-primary rather than the actual last "regular" CE before it,
      // for backward compatibility with behavior before the introduction of
      // script-first-primary CEs in the root collator.
      ce = rootElements.firstCEWithPrimaryAtLeast(
          baseData->getFirstPrimaryForGroup(USCRIPT_HAN));
      break;
  case CollationRuleParser::FIRST_IMPLICIT:
      ce = baseData->getSingleCE(0x4e00, errorCode);
      break;
  case CollationRuleParser::LAST_IMPLICIT:
      // We do not support tailoring to an unassigned-implicit CE.
      errorCode = U_UNSUPPORTED_ERROR;
      parserErrorReason = "reset to [last implicit] not supported";
      return 0;
  case CollationRuleParser::FIRST_TRAILING:
      ce = Collation::makeCE(Collation::FIRST_TRAILING_PRIMARY);
      isBoundary = TRUE1;  // trailing first primary (there is no mapping for it)
      break;
  case CollationRuleParser::LAST_TRAILING:
      errorCode = U_ILLEGAL_ARGUMENT_ERROR;
      parserErrorReason = "LDML forbids tailoring to U+FFFF";
      return 0;
  default:
      UPRV_UNREACHABLE_EXITabort();
  }

  int32_t index = findOrInsertNodeForRootCE(ce, strength, errorCode);
  if(U_FAILURE(errorCode)) { return 0; }
  int64_t node = nodes.elementAti(index);
  if((pos & 1) == 0) {
      // even pos = [first xyz]
      if(!nodeHasAnyBefore(node) && isBoundary) {
          // A <group> first primary boundary is artificially added to FractionalUCA.txt.
          // It is reachable via its special contraction, but is not normally used.
          // Find the first character tailored after the boundary CE,
          // or the first real root CE after it.
          if((index = nextIndexFromNode(node)) != 0) {
              // If there is a following node, then it must be tailored
              // because there are no root CEs with a boundary primary
              // and non-common secondary/tertiary weights.
              node = nodes.elementAti(index);
              U_ASSERT(isTailoredNode(node))(void)0;
              ce = tempCEFromIndexAndStrength(index, strength);
          } else {
              U_ASSERT(strength == UCOL_PRIMARY)(void)0;
              uint32_t p = (uint32_t)(ce >> 32);
              int32_t pIndex = rootElements.findPrimary(p);
              UBool isCompressible = baseData->isCompressiblePrimary(p);
              p = rootElements.getPrimaryAfter(p, pIndex, isCompressible);
              ce = Collation::makeCE(p);
              index = findOrInsertNodeForRootCE(ce, UCOL_PRIMARY, errorCode);
              if(U_FAILURE(errorCode)) { return 0; }
              node = nodes.elementAti(index);
          }
      }
      if(nodeHasAnyBefore(node)) {
          // Get the first node that was tailored before this one at a weaker strength.
          if(nodeHasBefore2(node)) {
              index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
              node = nodes.elementAti(index);
          }
          if(nodeHasBefore3(node)) {
              index = nextIndexFromNode(nodes.elementAti(nextIndexFromNode(node)));
          }
          U_ASSERT(isTailoredNode(nodes.elementAti(index)))(void)0;
          ce = tempCEFromIndexAndStrength(index, strength);
      }
  } else {
      // odd pos = [last xyz]
      // Find the last node that was tailored after the [last xyz]
      // at a strength no greater than the position's strength.
      for(;;) {
          int32_t nextIndex = nextIndexFromNode(node);
          if(nextIndex == 0) { break; }
          int64_t nextNode = nodes.elementAti(nextIndex);
          if(strengthFromNode(nextNode) < strength) { break; }
          index = nextIndex;
          node = nextNode;
      }
      // Do not make a temporary CE for a root node.
      // This last node might be the node for the root CE itself,
      // or a node with a common secondary or tertiary weight.
      if(isTailoredNode(node)) {
          ce = tempCEFromIndexAndStrength(index, strength);
      }
  }
  return ce;
644}

646void
647CollationBuilder::addRelation(int32_t strength, const UnicodeString &prefix,
                            const UnicodeString &str, const UnicodeString &extension,
                            const char *&parserErrorReason, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
  UnicodeString nfdPrefix;
  if(!prefix.isEmpty()) {
      nfd.normalize(prefix, nfdPrefix, errorCode);
      if(U_FAILURE(errorCode)) {
          parserErrorReason = "normalizing the relation prefix";
          return;
      }
  }
  UnicodeString nfdString = nfd.normalize(str, errorCode);
  if(U_FAILURE(errorCode)) {
      parserErrorReason = "normalizing the relation string";
      return;
  }

  // The runtime code decomposes Hangul syllables on the fly,
  // with recursive processing but without making the Jamo pieces visible for matching.
  // It does not work with certain types of contextual mappings.
  int32_t nfdLength = nfdString.length();
  if(nfdLength >= 2) {
      UChar c = nfdString.charAt(0);
      if(Hangul::isJamoL(c) || Hangul::isJamoV(c)) {
          // While handling a Hangul syllable, contractions starting with Jamo L or V
          // would not see the following Jamo of that syllable.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "contractions starting with conjoining Jamo L or V not supported";
          return;
      }
      c = nfdString.charAt(nfdLength - 1);
      if(Hangul::isJamoL(c) ||
              (Hangul::isJamoV(c) && Hangul::isJamoL(nfdString.charAt(nfdLength - 2)))) {
          // A contraction ending with Jamo L or L+V would require
          // generating Hangul syllables in addTailComposites() (588 for a Jamo L),
          // or decomposing a following Hangul syllable on the fly, during contraction matching.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "contractions ending with conjoining Jamo L or L+V not supported";
          return;
      }
      // A Hangul syllable completely inside a contraction is ok.
  }
  // Note: If there is a prefix, then the parser checked that
  // both the prefix and the string begin with NFC boundaries (not Jamo V or T).
  // Therefore: prefix.isEmpty() || !isJamoVOrT(nfdString.charAt(0))
  // (While handling a Hangul syllable, prefixes on Jamo V or T
  // would not see the previous Jamo of that syllable.)

  if(strength != UCOL_IDENTICAL) {
      // Find the node index after which we insert the new tailored node.
      int32_t index = findOrInsertNodeForCEs(strength, parserErrorReason, errorCode);
      U_ASSERT(cesLength > 0)(void)0;
      int64_t ce = ces[cesLength - 1];
      if(strength == UCOL_PRIMARY && !isTempCE(ce) && (uint32_t)(ce >> 32) == 0) {
          // There is no primary gap between ignorables and the space-first-primary.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "tailoring primary after ignorables not supported";
          return;
      }
      if(strength == UCOL_QUATERNARY && ce == 0) {
          // The CE data structure does not support non-zero quaternary weights
          // on tertiary ignorables.
          errorCode = U_UNSUPPORTED_ERROR;
          parserErrorReason = "tailoring quaternary after tertiary ignorables not supported";
          return;
      }
      // Insert the new tailored node.
      index = insertTailoredNodeAfter(index, strength, errorCode);
      if(U_FAILURE(errorCode)) {
          parserErrorReason = "modifying collation elements";
          return;
      }
      // Strength of the temporary CE:
      // The new relation may yield a stronger CE but not a weaker one.
      int32_t tempStrength = ceStrength(ce);
      if(strength < tempStrength) { tempStrength = strength; }
      ces[cesLength - 1] = tempCEFromIndexAndStrength(index, tempStrength);
  }

  setCaseBits(nfdString, parserErrorReason, errorCode);
  if(U_FAILURE(errorCode)) { return; }

  int32_t cesLengthBeforeExtension = cesLength;
  if(!extension.isEmpty()) {
      UnicodeString nfdExtension = nfd.normalize(extension, errorCode);
      if(U_FAILURE(errorCode)) {
          parserErrorReason = "normalizing the relation extension";
          return;
      }
      cesLength = dataBuilder->getCEs(nfdExtension, ces, cesLength);
      if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
          errorCode = U_ILLEGAL_ARGUMENT_ERROR;
          parserErrorReason =
              "extension string adds too many collation elements (more than 31 total)";
          return;
      }
  }
  uint32_t ce32 = Collation::UNASSIGNED_CE32;
  if((prefix != nfdPrefix || str != nfdString) &&
          !ignorePrefix(prefix, errorCode) && !ignoreString(str, errorCode)) {
      // Map from the original input to the CEs.
      // We do this in case the canonical closure is incomplete,
      // so that it is possible to explicitly provide the missing mappings.
      ce32 = addIfDifferent(prefix, str, ces, cesLength, ce32, errorCode);
  }
  addWithClosure(nfdPrefix, nfdString, ces, cesLength, ce32, errorCode);
  if(U_FAILURE(errorCode)) {
      parserErrorReason = "writing collation elements";
      return;
  }
  cesLength = cesLengthBeforeExtension;
759}

761int32_t
762CollationBuilder::findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,
                                       UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
9
←
Taking false branch→
  U_ASSERT(UCOL_PRIMARY <= strength && strength <= UCOL_QUATERNARY)(void)0;

  // Find the last CE that is at least as "strong" as the requested difference.
  // Note: Stronger is smaller (UCOL_PRIMARY=0).
  int64_t ce;
  for(;; --cesLength) {
10
←
Loop condition is true.  Entering loop body→
      if(cesLength == 0) {
11
←
Assuming field 'cesLength' is not equal to 0→
12
←
Taking false branch→
          ce = ces[0] = 0;
          cesLength = 1;
          break;
      } else {
          ce = ces[cesLength - 1];
      }
      if(ceStrength(ce) <= strength) { break; }
13
←
Assuming the condition is true→
14
←
Taking true branch→
  }

  if(isTempCE(ce)) {
16
←
Taking false branch→
      // No need to findCommonNode() here for lower levels
      // because insertTailoredNodeAfter() will do that anyway.
      return indexFromTempCE(ce);
  }

  // root CE
  if((uint8_t)(ce >> 56) == Collation::UNASSIGNED_IMPLICIT_BYTE) {
15
←
 Execution continues on line 781→
17
←
Assuming the condition is false→
18
←
Taking false branch→
      errorCode = U_UNSUPPORTED_ERROR;
      parserErrorReason = "tailoring relative to an unassigned code point not supported";
      return 0;
  }
  return findOrInsertNodeForRootCE(ce, strength, errorCode);
19
←
Calling 'CollationBuilder::findOrInsertNodeForRootCE'→
28
←
Returning from 'CollationBuilder::findOrInsertNodeForRootCE'→
794}

796int32_t
797CollationBuilder::findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
20
←
Taking false branch→
  U_ASSERT((uint8_t)(ce >> 56) != Collation::UNASSIGNED_IMPLICIT_BYTE)(void)0;

  // Find or insert the node for each of the root CE's weights,
  // down to the requested level/strength.
  // Root CEs must have common=zero quaternary weights (for which we never insert any nodes).
  U_ASSERT((ce & 0xc0) == 0)(void)0;
  int32_t index = findOrInsertNodeForPrimary((uint32_t)(ce >> 32), errorCode);
21
←
Calling 'CollationBuilder::findOrInsertNodeForPrimary'→
25
←
Returning from 'CollationBuilder::findOrInsertNodeForPrimary'→
  if(strength >= UCOL_SECONDARY) {
26
←
Assuming 'strength' is < UCOL_SECONDARY→
27
←
Taking false branch→
      uint32_t lower32 = (uint32_t)ce;
      index = findOrInsertWeakNode(index, lower32 >> 16, UCOL_SECONDARY, errorCode);
      if(strength >= UCOL_TERTIARY) {
          index = findOrInsertWeakNode(index, lower32 & Collation::ONLY_TERTIARY_MASK,
                                       UCOL_TERTIARY, errorCode);
      }
  }
  return index;
815}

817namespace {

819/**
* Like Java Collections.binarySearch(List, key, Comparator).
*
* @return the index>=0 where the item was found,
*         or the index<0 for inserting the string at ~index in sorted order
*         (index into rootPrimaryIndexes)
*/
826int32_t
827binarySearchForRootPrimaryNode(const int32_t *rootPrimaryIndexes, int32_t length,
                             const int64_t *nodes, uint32_t p) {
  if(length == 0) { return ~0; }
  int32_t start = 0;
  int32_t limit = length;
  for (;;) {
      int32_t i = (start + limit) / 2;
      int64_t node = nodes[rootPrimaryIndexes[i]];
      uint32_t nodePrimary = (uint32_t)(node >> 32);  // weight32FromNode(node)
      if (p == nodePrimary) {
          return i;
      } else if (p < nodePrimary) {
          if (i == start) {
              return ~start;  // insert s before i
          }
          limit = i;
      } else {
          if (i == start) {
              return ~(start + 1);  // insert s after i
          }
          start = i;
      }
  }
850}

852}  // namespace

854int32_t
855CollationBuilder::findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
22
←
Taking false branch→

  int32_t rootIndex = binarySearchForRootPrimaryNode(
      rootPrimaryIndexes.getBuffer(), rootPrimaryIndexes.size(), nodes.getBuffer(), p);
  if(rootIndex22.1
'rootIndex' is < 0
1
'rootIndex' is < 0
 >= 0) {
23
←
Taking false branch→
      return rootPrimaryIndexes.elementAti(rootIndex);
  } else {
      // Start a new list of nodes with this primary.
      int32_t index = nodes.size();
      nodes.addElement(nodeFromWeight32(p), errorCode);
      rootPrimaryIndexes.insertElementAt(index, ~rootIndex, errorCode);
24
←
Value assigned to field 'count'→
      return index;
  }
869}

871int32_t
872CollationBuilder::findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
  U_ASSERT(0 <= index && index < nodes.size())(void)0;
  U_ASSERT(UCOL_SECONDARY <= level && level <= UCOL_TERTIARY)(void)0;

  if(weight16 == Collation::COMMON_WEIGHT16) {
      return findCommonNode(index, level);
  }

  // If this will be the first below-common weight for the parent node,
  // then we will also need to insert a common weight after it.
  int64_t node = nodes.elementAti(index);
  U_ASSERT(strengthFromNode(node) < level)(void)0;  // parent node is stronger
  if(weight16 != 0 && weight16 < Collation::COMMON_WEIGHT16) {
      int32_t hasThisLevelBefore = level == UCOL_SECONDARY ? HAS_BEFORE2 : HAS_BEFORE3;
      if((node & hasThisLevelBefore) == 0) {
          // The parent node has an implied level-common weight.
          int64_t commonNode =
              nodeFromWeight16(Collation::COMMON_WEIGHT16) | nodeFromStrength(level);
          if(level == UCOL_SECONDARY) {
              // Move the HAS_BEFORE3 flag from the parent node
              // to the new secondary common node.
              commonNode |= node & HAS_BEFORE3;
              node &= ~(int64_t)HAS_BEFORE3;
          }
          nodes.setElementAt(node | hasThisLevelBefore, index);
          // Insert below-common-weight node.
          int32_t nextIndex = nextIndexFromNode(node);
          node = nodeFromWeight16(weight16) | nodeFromStrength(level);
          index = insertNodeBetween(index, nextIndex, node, errorCode);
          // Insert common-weight node.
          insertNodeBetween(index, nextIndex, commonNode, errorCode);
          // Return index of below-common-weight node.
          return index;
      }
  }

  // Find the root CE's weight for this level.
  // Postpone insertion if not found:
  // Insert the new root node before the next stronger node,
  // or before the next root node with the same strength and a larger weight.
  int32_t nextIndex;
  while((nextIndex = nextIndexFromNode(node)) != 0) {
      node = nodes.elementAti(nextIndex);
      int32_t nextStrength = strengthFromNode(node);
      if(nextStrength <= level) {
          // Insert before a stronger node.
          if(nextStrength < level) { break; }
          // nextStrength == level
          if(!isTailoredNode(node)) {
              uint32_t nextWeight16 = weight16FromNode(node);
              if(nextWeight16 == weight16) {
                  // Found the node for the root CE up to this level.
                  return nextIndex;
              }
              // Insert before a node with a larger same-strength weight.
              if(nextWeight16 > weight16) { break; }
          }
      }
      // Skip the next node.
      index = nextIndex;
  }
  node = nodeFromWeight16(weight16) | nodeFromStrength(level);
  return insertNodeBetween(index, nextIndex, node, errorCode);
936}

938int32_t
939CollationBuilder::insertTailoredNodeAfter(int32_t index, int32_t strength, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
  U_ASSERT(0 <= index && index < nodes.size())(void)0;
  if(strength >= UCOL_SECONDARY) {
      index = findCommonNode(index, UCOL_SECONDARY);
      if(strength >= UCOL_TERTIARY) {
          index = findCommonNode(index, UCOL_TERTIARY);
      }
  }
  // Postpone insertion:
  // Insert the new node before the next one with a strength at least as strong.
  int64_t node = nodes.elementAti(index);
  int32_t nextIndex;
  while((nextIndex = nextIndexFromNode(node)) != 0) {
      node = nodes.elementAti(nextIndex);
      if(strengthFromNode(node) <= strength) { break; }
      // Skip the next node which has a weaker (larger) strength than the new one.
      index = nextIndex;
  }
  node = IS_TAILORED | nodeFromStrength(strength);
  return insertNodeBetween(index, nextIndex, node, errorCode);
960}

962int32_t
963CollationBuilder::insertNodeBetween(int32_t index, int32_t nextIndex, int64_t node,
                                  UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return 0; }
48
←
Taking false branch→
  U_ASSERT(previousIndexFromNode(node) == 0)(void)0;
  U_ASSERT(nextIndexFromNode(node) == 0)(void)0;
  U_ASSERT(nextIndexFromNode(nodes.elementAti(index)) == nextIndex)(void)0;
  // Append the new node and link it to the existing nodes.
  int32_t newIndex = nodes.size();
49
←
'newIndex' initialized here→
  node |= nodeFromPreviousIndex(index) | nodeFromNextIndex(nextIndex);
  nodes.addElement(node, errorCode);
  if(U_FAILURE(errorCode)) { return 0; }
50
←
Taking false branch→
  // nodes[index].nextIndex = newIndex
  node = nodes.elementAti(index);
  nodes.setElementAt(changeNodeNextIndex(node, newIndex), index);
51
←
Passing the value 2147483647 via 2nd parameter 'next'→
52
←
Calling 'CollationBuilder::changeNodeNextIndex'→
  // nodes[nextIndex].previousIndex = newIndex
  if(nextIndex != 0) {
      node = nodes.elementAti(nextIndex);
      nodes.setElementAt(changeNodePreviousIndex(node, newIndex), nextIndex);
  }
  return newIndex;
983}

985int32_t
986CollationBuilder::findCommonNode(int32_t index, int32_t strength) const {
  U_ASSERT(UCOL_SECONDARY <= strength && strength <= UCOL_TERTIARY)(void)0;
  int64_t node = nodes.elementAti(index);
  if(strengthFromNode(node) >= strength) {
      // The current node is no stronger.
      return index;
  }
  if(strength == UCOL_SECONDARY ? !nodeHasBefore2(node) : !nodeHasBefore3(node)) {
      // The current node implies the strength-common weight.
      return index;
  }
  index = nextIndexFromNode(node);
  node = nodes.elementAti(index);
  U_ASSERT(!isTailoredNode(node) && strengthFromNode(node) == strength &&(void)0
          weight16FromNode(node) < Collation::COMMON_WEIGHT16)(void)0;
  // Skip to the explicit common node.
  do {
      index = nextIndexFromNode(node);
      node = nodes.elementAti(index);
      U_ASSERT(strengthFromNode(node) >= strength)(void)0;
  } while(isTailoredNode(node) || strengthFromNode(node) > strength ||
          weight16FromNode(node) < Collation::COMMON_WEIGHT16);
  U_ASSERT(weight16FromNode(node) == Collation::COMMON_WEIGHT16)(void)0;
  return index;
1010}

1012void
1013CollationBuilder::setCaseBits(const UnicodeString &nfdString,
                            const char *&parserErrorReason, UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
  int32_t numTailoredPrimaries = 0;
  for(int32_t i = 0; i < cesLength; ++i) {
      if(ceStrength(ces[i]) == UCOL_PRIMARY) { ++numTailoredPrimaries; }
  }
  // We should not be able to get too many case bits because
  // cesLength<=31==MAX_EXPANSION_LENGTH.
  // 31 pairs of case bits fit into an int64_t without setting its sign bit.
  U_ASSERT(numTailoredPrimaries <= 31)(void)0;

  int64_t cases = 0;
  if(numTailoredPrimaries > 0) {
      const UChar *s = nfdString.getBuffer();
      UTF16CollationIterator baseCEs(baseData, FALSE0, s, s, s + nfdString.length());
      int32_t baseCEsLength = baseCEs.fetchCEs(errorCode) - 1;
      if(U_FAILURE(errorCode)) {
          parserErrorReason = "fetching root CEs for tailored string";
          return;
      }
      U_ASSERT(baseCEsLength >= 0 && baseCEs.getCE(baseCEsLength) == Collation::NO_CE)(void)0;

      uint32_t lastCase = 0;
      int32_t numBasePrimaries = 0;
      for(int32_t i = 0; i < baseCEsLength; ++i) {
          int64_t ce = baseCEs.getCE(i);
          if((ce >> 32) != 0) {
              ++numBasePrimaries;
              uint32_t c = ((uint32_t)ce >> 14) & 3;
              U_ASSERT(c == 0 || c == 2)(void)0;  // lowercase or uppercase, no mixed case in any base CE
              if(numBasePrimaries < numTailoredPrimaries) {
                  cases |= (int64_t)c << ((numBasePrimaries - 1) * 2);
              } else if(numBasePrimaries == numTailoredPrimaries) {
                  lastCase = c;
              } else if(c != lastCase) {
                  // There are more base primary CEs than tailored primaries.
                  // Set mixed case if the case bits of the remainder differ.
                  lastCase = 1;
                  // Nothing more can change.
                  break;
              }
          }
      }
      if(numBasePrimaries >= numTailoredPrimaries) {
          cases |= (int64_t)lastCase << ((numTailoredPrimaries - 1) * 2);
      }
  }

  for(int32_t i = 0; i < cesLength; ++i) {
      int64_t ce = ces[i] & INT64_C(0xffffffffffff3fff)0xffffffffffff3fffL;  // clear old case bits
      int32_t strength = ceStrength(ce);
      if(strength == UCOL_PRIMARY) {
          ce |= (cases & 3) << 14;
          cases >>= 2;
      } else if(strength == UCOL_TERTIARY) {
          // Tertiary CEs must have uppercase bits.
          // See the LDML spec, and comments in class CollationCompare.
          ce |= 0x8000;
      }
      // Tertiary ignorable CEs must have 0 case bits.
      // We set 0 case bits for secondary CEs too
      // since currently only U+0345 is cased and maps to a secondary CE,
      // and it is lowercase. Other secondaries are uncased.
      // See [[:Cased:]&[:uca1=:]] where uca1 queries the root primary weight.
      ces[i] = ce;
  }
1080}

1082void
1083CollationBuilder::suppressContractions(const UnicodeSet &set, const char *&parserErrorReason,
                                     UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
  dataBuilder->suppressContractions(set, errorCode);
  if(U_FAILURE(errorCode)) {
      parserErrorReason = "application of [suppressContractions [set]] failed";
  }
1090}

1092void
1093CollationBuilder::optimize(const UnicodeSet &set, const char *& /* parserErrorReason */,
                         UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
  optimizeSet.addAll(set);
1097}

1099uint32_t
1100CollationBuilder::addWithClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                               const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                               UErrorCode &errorCode) {
  // Map from the NFD input to the CEs.
  ce32 = addIfDifferent(nfdPrefix, nfdString, newCEs, newCEsLength, ce32, errorCode);
  ce32 = addOnlyClosure(nfdPrefix, nfdString, newCEs, newCEsLength, ce32, errorCode);
  addTailComposites(nfdPrefix, nfdString, errorCode);
  return ce32;
1108}

1110uint32_t
1111CollationBuilder::addOnlyClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                               const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                               UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return ce32; }

  // Map from canonically equivalent input to the CEs. (But not from the all-NFD input.)
  if(nfdPrefix.isEmpty()) {
      CanonicalIterator stringIter(nfdString, errorCode);
      if(U_FAILURE(errorCode)) { return ce32; }
      UnicodeString prefix;
      for(;;) {
          UnicodeString str = stringIter.next();
          if(str.isBogus()) { break; }
          if(ignoreString(str, errorCode) || str == nfdString) { continue; }
          ce32 = addIfDifferent(prefix, str, newCEs, newCEsLength, ce32, errorCode);
          if(U_FAILURE(errorCode)) { return ce32; }
      }
  } else {
      CanonicalIterator prefixIter(nfdPrefix, errorCode);
      CanonicalIterator stringIter(nfdString, errorCode);
      if(U_FAILURE(errorCode)) { return ce32; }
      for(;;) {
          UnicodeString prefix = prefixIter.next();
          if(prefix.isBogus()) { break; }
          if(ignorePrefix(prefix, errorCode)) { continue; }
          UBool samePrefix = prefix == nfdPrefix;
          for(;;) {
              UnicodeString str = stringIter.next();
              if(str.isBogus()) { break; }
              if(ignoreString(str, errorCode) || (samePrefix && str == nfdString)) { continue; }
              ce32 = addIfDifferent(prefix, str, newCEs, newCEsLength, ce32, errorCode);
              if(U_FAILURE(errorCode)) { return ce32; }
          }
          stringIter.reset();
      }
  }
  return ce32;
1148}

1150void
1151CollationBuilder::addTailComposites(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                                  UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }

  // Look for the last starter in the NFD string.
  UChar32 lastStarter;
  int32_t indexAfterLastStarter = nfdString.length();
  for(;;) {
      if(indexAfterLastStarter == 0) { return; }  // no starter at all
      lastStarter = nfdString.char32At(indexAfterLastStarter - 1);
      if(nfd.getCombiningClass(lastStarter) == 0) { break; }
      indexAfterLastStarter -= U16_LENGTH(lastStarter)((uint32_t)(lastStarter)<=0xffff ? 1 : 2);
  }
  // No closure to Hangul syllables since we decompose them on the fly.
  if(Hangul::isJamoL(lastStarter)) { return; }

  // Are there any composites whose decomposition starts with the lastStarter?
  // Note: Normalizer2Impl does not currently return start sets for NFC_QC=Maybe characters.
  // We might find some more equivalent mappings here if it did.
  UnicodeSet composites;
  if(!nfcImpl.getCanonStartSet(lastStarter, composites)) { return; }

  UnicodeString decomp;
  UnicodeString newNFDString, newString;
  int64_t newCEs[Collation::MAX_EXPANSION_LENGTH];
  UnicodeSetIterator iter(composites);
  while(iter.next()) {
      U_ASSERT(!iter.isString())(void)0;
      UChar32 composite = iter.getCodepoint();
      nfd.getDecomposition(composite, decomp);
      if(!mergeCompositeIntoString(nfdString, indexAfterLastStarter, composite, decomp,
                                   newNFDString, newString, errorCode)) {
          continue;
      }
      int32_t newCEsLength = dataBuilder->getCEs(nfdPrefix, newNFDString, newCEs, 0);
      if(newCEsLength > Collation::MAX_EXPANSION_LENGTH) {
          // Ignore mappings that we cannot store.
          continue;
      }
      // Note: It is possible that the newCEs do not make use of the mapping
      // for which we are adding the tail composites, in which case we might be adding
      // unnecessary mappings.
      // For example, when we add tail composites for ae^ (^=combining circumflex),
      // UCA discontiguous-contraction matching does not find any matches
      // for ae_^ (_=any combining diacritic below) *unless* there is also
      // a contraction mapping for ae.
      // Thus, if there is no ae contraction, then the ae^ mapping is ignored
      // while fetching the newCEs for ae_^.
      // TODO: Try to detect this effectively.
      // (Alternatively, print a warning when prefix contractions are missing.)

      // We do not need an explicit mapping for the NFD strings.
      // It is fine if the NFD input collates like this via a sequence of mappings.
      // It also saves a little bit of space, and may reduce the set of characters with contractions.
      uint32_t ce32 = addIfDifferent(nfdPrefix, newString,
                                     newCEs, newCEsLength, Collation::UNASSIGNED_CE32, errorCode);
      if(ce32 != Collation::UNASSIGNED_CE32) {
          // was different, was added
          addOnlyClosure(nfdPrefix, newNFDString, newCEs, newCEsLength, ce32, errorCode);
      }
  }
1212}

1214UBool
1215CollationBuilder::mergeCompositeIntoString(const UnicodeString &nfdString,
                                         int32_t indexAfterLastStarter,
                                         UChar32 composite, const UnicodeString &decomp,
                                         UnicodeString &newNFDString, UnicodeString &newString,
                                         UErrorCode &errorCode) const {
  if(U_FAILURE(errorCode)) { return FALSE0; }
  U_ASSERT(nfdString.char32At(indexAfterLastStarter - 1) == decomp.char32At(0))(void)0;
  int32_t lastStarterLength = decomp.moveIndex32(0, 1);
  if(lastStarterLength == decomp.length()) {
      // Singleton decompositions should be found by addWithClosure()
      // and the CanonicalIterator, so we can ignore them here.
      return FALSE0;
  }
  if(nfdString.compare(indexAfterLastStarter, 0x7fffffff,
                       decomp, lastStarterLength, 0x7fffffff) == 0) {
      // same strings, nothing new to be found here
      return FALSE0;
  }

  // Make new FCD strings that combine a composite, or its decomposition,
  // into the nfdString's last starter and the combining marks following it.
  // Make an NFD version, and a version with the composite.
  newNFDString.setTo(nfdString, 0, indexAfterLastStarter);
  newString.setTo(nfdString, 0, indexAfterLastStarter - lastStarterLength).append(composite);

  // The following is related to discontiguous contraction matching,
  // but builds only FCD strings (or else returns FALSE).
  int32_t sourceIndex = indexAfterLastStarter;
  int32_t decompIndex = lastStarterLength;
  // Small optimization: We keep the source character across loop iterations
  // because we do not always consume it,
  // and then need not fetch it again nor look up its combining class again.
  UChar32 sourceChar = U_SENTINEL(-1);
  // The cc variables need to be declared before the loop so that at the end
  // they are set to the last combining classes seen.
  uint8_t sourceCC = 0;
  uint8_t decompCC = 0;
  for(;;) {
      if(sourceChar < 0) {
          if(sourceIndex >= nfdString.length()) { break; }
          sourceChar = nfdString.char32At(sourceIndex);
          sourceCC = nfd.getCombiningClass(sourceChar);
          U_ASSERT(sourceCC != 0)(void)0;
      }
      // We consume a decomposition character in each iteration.
      if(decompIndex >= decomp.length()) { break; }
      UChar32 decompChar = decomp.char32At(decompIndex);
      decompCC = nfd.getCombiningClass(decompChar);
      // Compare the two characters and their combining classes.
      if(decompCC == 0) {
          // Unable to merge because the source contains a non-zero combining mark
          // but the composite's decomposition contains another starter.
          // The strings would not be equivalent.
          return FALSE0;
      } else if(sourceCC < decompCC) {
          // Composite + sourceChar would not be FCD.
          return FALSE0;
      } else if(decompCC < sourceCC) {
          newNFDString.append(decompChar);
          decompIndex += U16_LENGTH(decompChar)((uint32_t)(decompChar)<=0xffff ? 1 : 2);
      } else if(decompChar != sourceChar) {
          // Blocked because same combining class.
          return FALSE0;
      } else {  // match: decompChar == sourceChar
          newNFDString.append(decompChar);
          decompIndex += U16_LENGTH(decompChar)((uint32_t)(decompChar)<=0xffff ? 1 : 2);
          sourceIndex += U16_LENGTH(decompChar)((uint32_t)(decompChar)<=0xffff ? 1 : 2);
          sourceChar = U_SENTINEL(-1);
      }
  }
  // We are at the end of at least one of the two inputs.
  if(sourceChar >= 0) {  // more characters from nfdString but not from decomp
      if(sourceCC < decompCC) {
          // Appending the next source character to the composite would not be FCD.
          return FALSE0;
      }
      newNFDString.append(nfdString, sourceIndex, 0x7fffffff);
      newString.append(nfdString, sourceIndex, 0x7fffffff);
  } else if(decompIndex < decomp.length()) {  // more characters from decomp, not from nfdString
      newNFDString.append(decomp, decompIndex, 0x7fffffff);
  }
  U_ASSERT(nfd.isNormalized(newNFDString, errorCode))(void)0;
  U_ASSERT(fcd.isNormalized(newString, errorCode))(void)0;
  U_ASSERT(nfd.normalize(newString, errorCode) == newNFDString)(void)0;  // canonically equivalent
  return TRUE1;
1300}

1302UBool
1303CollationBuilder::ignorePrefix(const UnicodeString &s, UErrorCode &errorCode) const {
  // Do not map non-FCD prefixes.
  return !isFCD(s, errorCode);
1306}

1308UBool
1309CollationBuilder::ignoreString(const UnicodeString &s, UErrorCode &errorCode) const {
  // Do not map non-FCD strings.
  // Do not map strings that start with Hangul syllables: We decompose those on the fly.
  return !isFCD(s, errorCode) || Hangul::isHangul(s.charAt(0));
1313}

1315UBool
1316CollationBuilder::isFCD(const UnicodeString &s, UErrorCode &errorCode) const {
  return U_SUCCESS(errorCode) && fcd.isNormalized(s, errorCode);
1318}

1320void
1321CollationBuilder::closeOverComposites(UErrorCode &errorCode) {
  UnicodeSet composites(UNICODE_STRING_SIMPLE("[:NFD_QC=N:]")icu::UnicodeString(true, u"[:NFD_QC=N:]", -1), errorCode);  // Java: static final
  if(U_FAILURE(errorCode)) { return; }
  // Hangul is decomposed on the fly during collation.
  composites.remove(Hangul::HANGUL_BASE, Hangul::HANGUL_END);
  UnicodeString prefix;  // empty
  UnicodeString nfdString;
  UnicodeSetIterator iter(composites);
  while(iter.next()) {
      U_ASSERT(!iter.isString())(void)0;
      nfd.getDecomposition(iter.getCodepoint(), nfdString);
      cesLength = dataBuilder->getCEs(nfdString, ces, 0);
      if(cesLength > Collation::MAX_EXPANSION_LENGTH) {
          // Too many CEs from the decomposition (unusual), ignore this composite.
          // We could add a capacity parameter to getCEs() and reallocate if necessary.
          // However, this can only really happen in contrived cases.
          continue;
      }
      const UnicodeString &composite(iter.getString());
      addIfDifferent(prefix, composite, ces, cesLength, Collation::UNASSIGNED_CE32, errorCode);
  }
1342}

1344uint32_t
1345CollationBuilder::addIfDifferent(const UnicodeString &prefix, const UnicodeString &str,
                               const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                               UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return ce32; }
  int64_t oldCEs[Collation::MAX_EXPANSION_LENGTH];
  int32_t oldCEsLength = dataBuilder->getCEs(prefix, str, oldCEs, 0);
  if(!sameCEs(newCEs, newCEsLength, oldCEs, oldCEsLength)) {
      if(ce32 == Collation::UNASSIGNED_CE32) {
          ce32 = dataBuilder->encodeCEs(newCEs, newCEsLength, errorCode);
      }
      dataBuilder->addCE32(prefix, str, ce32, errorCode);
  }
  return ce32;
1358}

1360UBool
1361CollationBuilder::sameCEs(const int64_t ces1[], int32_t ces1Length,
                        const int64_t ces2[], int32_t ces2Length) {
  if(ces1Length != ces2Length) {
      return FALSE0;
  }
  U_ASSERT(ces1Length <= Collation::MAX_EXPANSION_LENGTH)(void)0;
  for(int32_t i = 0; i < ces1Length; ++i) {
      if(ces1[i] != ces2[i]) { return FALSE0; }
  }
  return TRUE1;
1371}

1373#ifdef DEBUG_COLLATION_BUILDER

1375uint32_t
1376alignWeightRight(uint32_t w) {
  if(w != 0) {
      while((w & 0xff) == 0) { w >>= 8; }
  }
  return w;
1381}

1383#endif

1385void
1386CollationBuilder::makeTailoredCEs(UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }

  CollationWeights primaries, secondaries, tertiaries;
  int64_t *nodesArray = nodes.getBuffer();
1391#ifdef DEBUG_COLLATION_BUILDER
      puts("\nCollationBuilder::makeTailoredCEs()");
1393#endif

  for(int32_t rpi = 0; rpi < rootPrimaryIndexes.size(); ++rpi) {
      int32_t i = rootPrimaryIndexes.elementAti(rpi);
      int64_t node = nodesArray[i];
      uint32_t p = weight32FromNode(node);
      uint32_t s = p == 0 ? 0 : Collation::COMMON_WEIGHT16;
      uint32_t t = s;
      uint32_t q = 0;
      UBool pIsTailored = FALSE0;
      UBool sIsTailored = FALSE0;
      UBool tIsTailored = FALSE0;
1405#ifdef DEBUG_COLLATION_BUILDER
      printf("\nprimary     %lx\n", (long)alignWeightRight(p));
1407#endif
      int32_t pIndex = p == 0 ? 0 : rootElements.findPrimary(p);
      int32_t nextIndex = nextIndexFromNode(node);
      while(nextIndex != 0) {
          i = nextIndex;
          node = nodesArray[i];
          nextIndex = nextIndexFromNode(node);
          int32_t strength = strengthFromNode(node);
          if(strength == UCOL_QUATERNARY) {
              U_ASSERT(isTailoredNode(node))(void)0;
1417#ifdef DEBUG_COLLATION_BUILDER
              printf("      quat+     ");
1419#endif
              if(q == 3) {
                  errorCode = U_BUFFER_OVERFLOW_ERROR;
                  errorReason = "quaternary tailoring gap too small";
                  return;
              }
              ++q;
          } else {
              if(strength == UCOL_TERTIARY) {
                  if(isTailoredNode(node)) {
1429#ifdef DEBUG_COLLATION_BUILDER
                      printf("    ter+        ");
1431#endif
                      if(!tIsTailored) {
                          // First tailored tertiary node for [p, s].
                          int32_t tCount = countTailoredNodes(nodesArray, nextIndex,
                                                              UCOL_TERTIARY) + 1;
                          uint32_t tLimit;
                          if(t == 0) {
                              // Gap at the beginning of the tertiary CE range.
                              t = rootElements.getTertiaryBoundary() - 0x100;
                              tLimit = rootElements.getFirstTertiaryCE() & Collation::ONLY_TERTIARY_MASK;
                          } else if(!pIsTailored && !sIsTailored) {
                              // p and s are root weights.
                              tLimit = rootElements.getTertiaryAfter(pIndex, s, t);
                          } else if(t == Collation::BEFORE_WEIGHT16) {
                              tLimit = Collation::COMMON_WEIGHT16;
                          } else {
                              // [p, s] is tailored.
                              U_ASSERT(t == Collation::COMMON_WEIGHT16)(void)0;
                              tLimit = rootElements.getTertiaryBoundary();
                          }
                          U_ASSERT(tLimit == 0x4000 || (tLimit & ~Collation::ONLY_TERTIARY_MASK) == 0)(void)0;
                          tertiaries.initForTertiary();
                          if(!tertiaries.allocWeights(t, tLimit, tCount)) {
                              errorCode = U_BUFFER_OVERFLOW_ERROR;
                              errorReason = "tertiary tailoring gap too small";
                              return;
                          }
                          tIsTailored = TRUE1;
                      }
                      t = tertiaries.nextWeight();
                      U_ASSERT(t != 0xffffffff)(void)0;
                  } else {
                      t = weight16FromNode(node);
                      tIsTailored = FALSE0;
1465#ifdef DEBUG_COLLATION_BUILDER
                      printf("    ter     %lx\n", (long)alignWeightRight(t));
1467#endif
                  }
              } else {
                  if(strength == UCOL_SECONDARY) {
                      if(isTailoredNode(node)) {
1472#ifdef DEBUG_COLLATION_BUILDER
                          printf("  sec+          ");
1474#endif
                          if(!sIsTailored) {
                              // First tailored secondary node for p.
                              int32_t sCount = countTailoredNodes(nodesArray, nextIndex,
                                                                  UCOL_SECONDARY) + 1;
                              uint32_t sLimit;
                              if(s == 0) {
                                  // Gap at the beginning of the secondary CE range.
                                  s = rootElements.getSecondaryBoundary() - 0x100;
                                  sLimit = rootElements.getFirstSecondaryCE() >> 16;
                              } else if(!pIsTailored) {
                                  // p is a root primary.
                                  sLimit = rootElements.getSecondaryAfter(pIndex, s);
                              } else if(s == Collation::BEFORE_WEIGHT16) {
                                  sLimit = Collation::COMMON_WEIGHT16;
                              } else {
                                  // p is a tailored primary.
                                  U_ASSERT(s == Collation::COMMON_WEIGHT16)(void)0;
                                  sLimit = rootElements.getSecondaryBoundary();
                              }
                              if(s == Collation::COMMON_WEIGHT16) {
                                  // Do not tailor into the getSortKey() range of
                                  // compressed common secondaries.
                                  s = rootElements.getLastCommonSecondary();
                              }
                              secondaries.initForSecondary();
                              if(!secondaries.allocWeights(s, sLimit, sCount)) {
                                  errorCode = U_BUFFER_OVERFLOW_ERROR;
                                  errorReason = "secondary tailoring gap too small";
1503#ifdef DEBUG_COLLATION_BUILDER
                                  printf("!secondaries.allocWeights(%lx, %lx, sCount=%ld)\n",
                                         (long)alignWeightRight(s), (long)alignWeightRight(sLimit),
                                         (long)alignWeightRight(sCount));
1507#endif
                                  return;
                              }
                              sIsTailored = TRUE1;
                          }
                          s = secondaries.nextWeight();
                          U_ASSERT(s != 0xffffffff)(void)0;
                      } else {
                          s = weight16FromNode(node);
                          sIsTailored = FALSE0;
1517#ifdef DEBUG_COLLATION_BUILDER
                          printf("  sec       %lx\n", (long)alignWeightRight(s));
1519#endif
                      }
                  } else /* UCOL_PRIMARY */ {
                      U_ASSERT(isTailoredNode(node))(void)0;
1523#ifdef DEBUG_COLLATION_BUILDER
                      printf("pri+            ");
1525#endif
                      if(!pIsTailored) {
                          // First tailored primary node in this list.
                          int32_t pCount = countTailoredNodes(nodesArray, nextIndex,
                                                              UCOL_PRIMARY) + 1;
                          UBool isCompressible = baseData->isCompressiblePrimary(p);
                          uint32_t pLimit =
                              rootElements.getPrimaryAfter(p, pIndex, isCompressible);
                          primaries.initForPrimary(isCompressible);
                          if(!primaries.allocWeights(p, pLimit, pCount)) {
                              errorCode = U_BUFFER_OVERFLOW_ERROR;  // TODO: introduce a more specific UErrorCode?
                              errorReason = "primary tailoring gap too small";
                              return;
                          }
                          pIsTailored = TRUE1;
                      }
                      p = primaries.nextWeight();
                      U_ASSERT(p != 0xffffffff)(void)0;
                      s = Collation::COMMON_WEIGHT16;
                      sIsTailored = FALSE0;
                  }
                  t = s == 0 ? 0 : Collation::COMMON_WEIGHT16;
                  tIsTailored = FALSE0;
              }
              q = 0;
          }
          if(isTailoredNode(node)) {
              nodesArray[i] = Collation::makeCE(p, s, t, q);
1553#ifdef DEBUG_COLLATION_BUILDER
              printf("%016llx\n", (long long)nodesArray[i]);
1555#endif
          }
      }
  }
1559}

1561int32_t
1562CollationBuilder::countTailoredNodes(const int64_t *nodesArray, int32_t i, int32_t strength) {
  int32_t count = 0;
  for(;;) {
      if(i == 0) { break; }
      int64_t node = nodesArray[i];
      if(strengthFromNode(node) < strength) { break; }
      if(strengthFromNode(node) == strength) {
          if(isTailoredNode(node)) {
              ++count;
          } else {
              break;
          }
      }
      i = nextIndexFromNode(node);
  }
  return count;
1578}

1580class CEFinalizer : public CollationDataBuilder::CEModifier {
1581public:
  CEFinalizer(const int64_t *ces) : finalCEs(ces) {}
  virtual ~CEFinalizer();
  virtual int64_t modifyCE32(uint32_t ce32) const override {
      U_ASSERT(!Collation::isSpecialCE32(ce32))(void)0;
      if(CollationBuilder::isTempCE32(ce32)) {
          // retain case bits
          return finalCEs[CollationBuilder::indexFromTempCE32(ce32)] | ((ce32 & 0xc0) << 8);
      } else {
          return Collation::NO_CE;
      }
  }
  virtual int64_t modifyCE(int64_t ce) const override {
      if(CollationBuilder::isTempCE(ce)) {
          // retain case bits
          return finalCEs[CollationBuilder::indexFromTempCE(ce)] | (ce & 0xc000);
      } else {
          return Collation::NO_CE;
      }
  }

1602private:
  const int64_t *finalCEs;
1604};

1606CEFinalizer::~CEFinalizer() {}

1608void
1609CollationBuilder::finalizeCEs(UErrorCode &errorCode) {
  if(U_FAILURE(errorCode)) { return; }
  LocalPointer<CollationDataBuilder> newBuilder(new CollationDataBuilder(errorCode), errorCode);
  if(U_FAILURE(errorCode)) {
      return;
  }
  newBuilder->initForTailoring(baseData, errorCode);
  CEFinalizer finalizer(nodes.getBuffer());
  newBuilder->copyFrom(*dataBuilder, finalizer, errorCode);
  if(U_FAILURE(errorCode)) { return; }
  delete dataBuilder;
  dataBuilder = newBuilder.orphan();
1621}

1623int32_t
1624CollationBuilder::ceStrength(int64_t ce) {
  return
      isTempCE(ce) ? strengthFromTempCE(ce) :
      (ce & INT64_C(0xff00000000000000)0xff00000000000000L) != 0 ? UCOL_PRIMARY :
      ((uint32_t)ce & 0xff000000) != 0 ? UCOL_SECONDARY :
      ce != 0 ? UCOL_TERTIARY :
      UCOL_IDENTICAL;
1631}

1633U_NAMESPACE_END}

1635U_NAMESPACE_USEusing namespace icu_71;

1637U_CAPIextern "C" UCollator * U_EXPORT2
1638ucol_openRulesucol_openRules_71(const UChar *rules, int32_t rulesLength,
             UColAttributeValue normalizationMode, UCollationStrength strength,
             UParseError *parseError, UErrorCode *pErrorCode) {
  if(U_FAILURE(*pErrorCode)) { return NULL__null; }
  if(rules == NULL__null && rulesLength != 0) {
      *pErrorCode = U_ILLEGAL_ARGUMENT_ERROR;
      return NULL__null;
  }
  RuleBasedCollator *coll = new RuleBasedCollator();
  if(coll == NULL__null) {
      *pErrorCode = U_MEMORY_ALLOCATION_ERROR;
      return NULL__null;
  }
  UnicodeString r((UBool)(rulesLength < 0), rules, rulesLength);
  coll->internalBuildTailoring(r, strength, normalizationMode, parseError, NULL__null, *pErrorCode);
  if(U_FAILURE(*pErrorCode)) {
      delete coll;
      return NULL__null;
  }
  return coll->toUCollator();
1658}

1660static const int32_t internalBufferSize = 512;

1662// The @internal ucol_getUnsafeSet() was moved here from ucol_sit.cpp
1663// because it calls UnicodeSet "builder" code that depends on all Unicode properties,
1664// and the rest of the collation "runtime" code only depends on normalization.
1665// This function is not related to the collation builder,
1666// but it did not seem worth moving it into its own .cpp file,
1667// nor rewriting it to use lower-level UnicodeSet and Normalizer2Impl methods.
1668U_CAPIextern "C" int32_t U_EXPORT2
1669ucol_getUnsafeSetucol_getUnsafeSet_71( const UCollator *coll,
                USet *unsafe,
                UErrorCode *status)
1672{
  UChar buffer[internalBufferSize];
  int32_t len = 0;

  uset_clearuset_clear_71(unsafe);

  // cccpattern = "[[:^tccc=0:][:^lccc=0:]]", unfortunately variant
  static const UChar cccpattern[25] = { 0x5b, 0x5b, 0x3a, 0x5e, 0x74, 0x63, 0x63, 0x63, 0x3d, 0x30, 0x3a, 0x5d,
                                  0x5b, 0x3a, 0x5e, 0x6c, 0x63, 0x63, 0x63, 0x3d, 0x30, 0x3a, 0x5d, 0x5d, 0x00 };

  // add chars that fail the fcd check
  uset_applyPatternuset_applyPattern_71(unsafe, cccpattern, 24, USET_IGNORE_SPACE, status);

  // add lead/trail surrogates
  // (trail surrogates should need to be unsafe only if the caller tests for UTF-16 code *units*,
  // not when testing code *points*)
  uset_addRangeuset_addRange_71(unsafe, 0xd800, 0xdfff);

  USet *contractions = uset_openuset_open_71(0,0);

  int32_t i = 0, j = 0;
  ucol_getContractionsAndExpansionsucol_getContractionsAndExpansions_71(coll, contractions, NULL__null, FALSE0, status);
  int32_t contsSize = uset_sizeuset_size_71(contractions);
  UChar32 c = 0;
  // Contraction set consists only of strings
  // to get unsafe code points, we need to
  // break the strings apart and add them to the unsafe set
  for(i = 0; i < contsSize; i++) {
      len = uset_getItemuset_getItem_71(contractions, i, NULL__null, NULL__null, buffer, internalBufferSize, status);
      if(len > 0) {
          j = 0;
          while(j < len) {
              U16_NEXT(buffer, j, len, c)do { (c)=(buffer)[(j)++]; if((((c)&0xfffffc00)==0xd800)) {
 uint16_t __c2; if((j)!=(len) && (((__c2=(buffer)[(j)
])&0xfffffc00)==0xdc00)) { ++(j); (c)=(((UChar32)((c))<<
10UL)+(UChar32)(__c2)-((0xd800<<10UL)+0xdc00-0x10000));
 } } } while (false);
              if(j < len) {
                  uset_adduset_add_71(unsafe, c);
              }
          }
      }
  }

  uset_closeuset_close_71(contractions);

  return uset_sizeuset_size_71(unsafe);
1715}

1717#endif  // !UCONFIG_NO_COLLATION

←

../deps/icu-small/source/i18n/collationbuilder.h

1// © 2016 and later: Unicode, Inc. and others.
2// License & terms of use: http://www.unicode.org/copyright.html
3/*
4*******************************************************************************
5* Copyright (C) 2013-2014, International Business Machines
6* Corporation and others.  All Rights Reserved.
7*******************************************************************************
8* collationbuilder.h
9*
10* created on: 2013may06
11* created by: Markus W. Scherer
12*/

14#ifndef __COLLATIONBUILDER_H__
15#define __COLLATIONBUILDER_H__

17#include "unicode/utypes.h"

19#if !UCONFIG_NO_COLLATION0

21#include "unicode/uniset.h"
22#include "unicode/unistr.h"
23#include "collationrootelements.h"
24#include "collationruleparser.h"
25#include "uvectr32.h"
26#include "uvectr64.h"

28struct UParseError;

30U_NAMESPACE_BEGINnamespace icu_71 {

32struct CollationData;
33struct CollationTailoring;

35class CEFinalizer;
36class CollationDataBuilder;
37class Normalizer2;
38class Normalizer2Impl;

40class U_I18N_API CollationBuilder : public CollationRuleParser::Sink {
41public:
  CollationBuilder(const CollationTailoring *base, UErrorCode &errorCode);
  virtual ~CollationBuilder();

  void disableFastLatin() { fastLatinEnabled = false; }

  CollationTailoring *parseAndBuild(const UnicodeString &ruleString,
                                    const UVersionInfo rulesVersion,
                                    CollationRuleParser::Importer *importer,
                                    UParseError *outParseError,
                                    UErrorCode &errorCode);

  const char *getErrorReason() const { return errorReason; }

55private:
  friend class CEFinalizer;

  /** Implements CollationRuleParser::Sink. */
  virtual void addReset(int32_t strength, const UnicodeString &str,
                        const char *&errorReason, UErrorCode &errorCode) override;
  /**
   * Returns the secondary or tertiary weight preceding the current node's weight.
   * node=nodes[index].
   */
  uint32_t getWeight16Before(int32_t index, int64_t node, int32_t level);

  int64_t getSpecialResetPosition(const UnicodeString &str,
                                  const char *&parserErrorReason, UErrorCode &errorCode);

  /** Implements CollationRuleParser::Sink. */
  virtual void addRelation(int32_t strength, const UnicodeString &prefix,
                           const UnicodeString &str, const UnicodeString &extension,
                           const char *&errorReason, UErrorCode &errorCode) override;

  /**
   * Picks one of the current CEs and finds or inserts a node in the graph
   * for the CE + strength.
   */
  int32_t findOrInsertNodeForCEs(int32_t strength, const char *&parserErrorReason,
                                 UErrorCode &errorCode);
  int32_t findOrInsertNodeForRootCE(int64_t ce, int32_t strength, UErrorCode &errorCode);
  /** Finds or inserts the node for a root CE's primary weight. */
  int32_t findOrInsertNodeForPrimary(uint32_t p, UErrorCode &errorCode);
  /** Finds or inserts the node for a secondary or tertiary weight. */
  int32_t findOrInsertWeakNode(int32_t index, uint32_t weight16, int32_t level,
                               UErrorCode &errorCode);

  /**
   * Makes and inserts a new tailored node into the list, after the one at index.
   * Skips over nodes of weaker strength to maintain collation order
   * ("postpone insertion").
   * @return the new node's index
   */
  int32_t insertTailoredNodeAfter(int32_t index, int32_t strength, UErrorCode &errorCode);

  /**
   * Inserts a new node into the list, between list-adjacent items.
   * The node's previous and next indexes must not be set yet.
   * @return the new node's index
   */
  int32_t insertNodeBetween(int32_t index, int32_t nextIndex, int64_t node,
                            UErrorCode &errorCode);

  /**
   * Finds the node which implies or contains a common=05 weight of the given strength
   * (secondary or tertiary), if the current node is stronger.
   * Skips weaker nodes and tailored nodes if the current node is stronger
   * and is followed by an explicit-common-weight node.
   * Always returns the input index if that node is no stronger than the given strength.
   */
  int32_t findCommonNode(int32_t index, int32_t strength) const;

  void setCaseBits(const UnicodeString &nfdString,
                   const char *&parserErrorReason, UErrorCode &errorCode);

  /** Implements CollationRuleParser::Sink. */
  virtual void suppressContractions(const UnicodeSet &set, const char *&parserErrorReason,
                                    UErrorCode &errorCode) override;

  /** Implements CollationRuleParser::Sink. */
  virtual void optimize(const UnicodeSet &set, const char *&parserErrorReason,
                        UErrorCode &errorCode) override;

  /**
   * Adds the mapping and its canonical closure.
   * Takes ce32=dataBuilder->encodeCEs(...) so that the data builder
   * need not re-encode the CEs multiple times.
   */
  uint32_t addWithClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                          const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                          UErrorCode &errorCode);
  uint32_t addOnlyClosure(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                          const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                          UErrorCode &errorCode);
  void addTailComposites(const UnicodeString &nfdPrefix, const UnicodeString &nfdString,
                         UErrorCode &errorCode);
  UBool mergeCompositeIntoString(const UnicodeString &nfdString, int32_t indexAfterLastStarter,
                                 UChar32 composite, const UnicodeString &decomp,
                                 UnicodeString &newNFDString, UnicodeString &newString,
                                 UErrorCode &errorCode) const;

  UBool ignorePrefix(const UnicodeString &s, UErrorCode &errorCode) const;
  UBool ignoreString(const UnicodeString &s, UErrorCode &errorCode) const;
  UBool isFCD(const UnicodeString &s, UErrorCode &errorCode) const;

  void closeOverComposites(UErrorCode &errorCode);

  uint32_t addIfDifferent(const UnicodeString &prefix, const UnicodeString &str,
                          const int64_t newCEs[], int32_t newCEsLength, uint32_t ce32,
                          UErrorCode &errorCode);
  static UBool sameCEs(const int64_t ces1[], int32_t ces1Length,
                       const int64_t ces2[], int32_t ces2Length);

  /**
   * Walks the tailoring graph and overwrites tailored nodes with new CEs.
   * After this, the graph is destroyed.
   * The nodes array can then be used only as a source of tailored CEs.
   */
  void makeTailoredCEs(UErrorCode &errorCode);
  /**
   * Counts the tailored nodes of the given strength up to the next node
   * which is either stronger or has an explicit weight of this strength.
   */
  static int32_t countTailoredNodes(const int64_t *nodesArray, int32_t i, int32_t strength);

  /** Replaces temporary CEs with the final CEs they point to. */
  void finalizeCEs(UErrorCode &errorCode);

  /**
   * Encodes "temporary CE" data into a CE that fits into the CE32 data structure,
   * with 2-byte primary, 1-byte secondary and 6-bit tertiary,
   * with valid CE byte values.
   *
   * The index must not exceed 20 bits (0xfffff).
   * The strength must fit into 2 bits (UCOL_PRIMARY..UCOL_QUATERNARY).
   *
   * Temporary CEs are distinguished from real CEs by their use of
   * secondary weights 06..45 which are otherwise reserved for compressed sort keys.
   *
   * The case bits are unused and available.
   */
  static inline int64_t tempCEFromIndexAndStrength(int32_t index, int32_t strength) {
      return
          // CE byte offsets, to ensure valid CE bytes, and case bits 11
          INT64_C(0x4040000006002000)0x4040000006002000L +
          // index bits 19..13 -> primary byte 1 = CE bits 63..56 (byte values 40..BF)
          ((int64_t)(index & 0xfe000) << 43) +
          // index bits 12..6 -> primary byte 2 = CE bits 55..48 (byte values 40..BF)
          ((int64_t)(index & 0x1fc0) << 42) +
          // index bits 5..0 -> secondary byte 1 = CE bits 31..24 (byte values 06..45)
          ((index & 0x3f) << 24) +
          // strength bits 1..0 -> tertiary byte 1 = CE bits 13..8 (byte values 20..23)
          (strength << 8);
  }
  static inline int32_t indexFromTempCE(int64_t tempCE) {
      tempCE -= INT64_C(0x4040000006002000)0x4040000006002000L;
      return
          ((int32_t)(tempCE >> 43) & 0xfe000) |
          ((int32_t)(tempCE >> 42) & 0x1fc0) |
          ((int32_t)(tempCE >> 24) & 0x3f);
  }
  static inline int32_t strengthFromTempCE(int64_t tempCE) {
      return ((int32_t)tempCE >> 8) & 3;
  }
  static inline UBool isTempCE(int64_t ce) {
      uint32_t sec = (uint32_t)ce >> 24;
      return 6 <= sec && sec <= 0x45;
  }

  static inline int32_t indexFromTempCE32(uint32_t tempCE32) {
      tempCE32 -= 0x40400620;
      return
          ((int32_t)(tempCE32 >> 11) & 0xfe000) |
          ((int32_t)(tempCE32 >> 10) & 0x1fc0) |
          ((int32_t)(tempCE32 >> 8) & 0x3f);
  }
  static inline UBool isTempCE32(uint32_t ce32) {
      return
          (ce32 & 0xff) >= 2 &&  // not a long-primary/long-secondary CE32
          6 <= ((ce32 >> 8) & 0xff) && ((ce32 >> 8) & 0xff) <= 0x45;
  }

  static int32_t ceStrength(int64_t ce);

  /** At most 1M nodes, limited by the 20 bits in node bit fields. */
  static const int32_t MAX_INDEX = 0xfffff;
  /**
   * Node bit 6 is set on a primary node if there are nodes
   * with secondary values below the common secondary weight (05).
   */
  static const int32_t HAS_BEFORE2 = 0x40;
  /**
   * Node bit 5 is set on a primary or secondary node if there are nodes
   * with tertiary values below the common tertiary weight (05).
   */
  static const int32_t HAS_BEFORE3 = 0x20;
  /**
   * Node bit 3 distinguishes a tailored node, which has no weight value,
   * from a node with an explicit (root or default) weight.
   */
  static const int32_t IS_TAILORED = 8;

  static inline int64_t nodeFromWeight32(uint32_t weight32) {
      return (int64_t)weight32 << 32;
  }
  static inline int64_t nodeFromWeight16(uint32_t weight16) {
      return (int64_t)weight16 << 48;
  }
  static inline int64_t nodeFromPreviousIndex(int32_t previous) {
      return (int64_t)previous << 28;
  }
  static inline int64_t nodeFromNextIndex(int32_t next) {
      return next << 8;
55
←
The result of the left shift is undefined due to shifting '2147483647' by '8', which is unrepresentable in the unsigned version of the return type 'int32_t'
  }
  static inline int64_t nodeFromStrength(int32_t strength) {
      return strength;
  }

  static inline uint32_t weight32FromNode(int64_t node) {
      return (uint32_t)(node >> 32);
  }
  static inline uint32_t weight16FromNode(int64_t node) {
      return (uint32_t)(node >> 48) & 0xffff;
  }
  static inline int32_t previousIndexFromNode(int64_t node) {
      return (int32_t)(node >> 28) & MAX_INDEX;
  }
  static inline int32_t nextIndexFromNode(int64_t node) {
      return ((int32_t)node >> 8) & MAX_INDEX;
  }
  static inline int32_t strengthFromNode(int64_t node) {
      return (int32_t)node & 3;
  }

  static inline UBool nodeHasBefore2(int64_t node) {
      return (node & HAS_BEFORE2) != 0;
  }
  static inline UBool nodeHasBefore3(int64_t node) {
      return (node & HAS_BEFORE3) != 0;
  }
  static inline UBool nodeHasAnyBefore(int64_t node) {
      return (node & (HAS_BEFORE2 | HAS_BEFORE3)) != 0;
  }
  static inline UBool isTailoredNode(int64_t node) {
      return (node & IS_TAILORED) != 0;
  }

  static inline int64_t changeNodePreviousIndex(int64_t node, int32_t previous) {
      return (node & INT64_C(0xffff00000fffffff)0xffff00000fffffffL) | nodeFromPreviousIndex(previous);
  }
  static inline int64_t changeNodeNextIndex(int64_t node, int32_t next) {
      return (node & INT64_C(0xfffffffff00000ff)0xfffffffff00000ffL) | nodeFromNextIndex(next);
53
←
Passing the value 2147483647 via 1st parameter 'next'→
54
←
Calling 'CollationBuilder::nodeFromNextIndex'→
  }

  const Normalizer2 &nfd, &fcd;
  const Normalizer2Impl &nfcImpl;

  const CollationTailoring *base;
  const CollationData *baseData;
  const CollationRootElements rootElements;
  uint32_t variableTop;

  CollationDataBuilder *dataBuilder;
  UBool fastLatinEnabled;
  UnicodeSet optimizeSet;
  const char *errorReason;

  int64_t ces[Collation::MAX_EXPANSION_LENGTH];
  int32_t cesLength;

  /**
   * Indexes of nodes with root primary weights, sorted by primary.
   * Compact form of a TreeMap from root primary to node index.
   *
   * This is a performance optimization for finding reset positions.
   * Without this, we would have to search through the entire nodes list.
   * It also allows storing root primary weights in list head nodes,
   * without previous index, leaving room in root primary nodes for 32-bit primary weights.
   */
  UVector32 rootPrimaryIndexes;
  /**
   * Data structure for assigning tailored weights and CEs.
   * Doubly-linked lists of nodes in mostly collation order.
   * Each list starts with a root primary node and ends with a nextIndex of 0.
   *
   * When there are any nodes in the list, then there is always a root primary node at index 0.
   * This allows some code not to have to check explicitly for nextIndex==0.
   *
   * Root primary nodes have 32-bit weights but do not have previous indexes.
   * All other nodes have at most 16-bit weights and do have previous indexes.
   *
   * Nodes with explicit weights store root collator weights,
   * or default weak weights (e.g., secondary 05) for stronger nodes.
   * "Tailored" nodes, with the IS_TAILORED bit set,
   * do not store explicit weights but rather
   * create a difference of a certain strength from the preceding node.
   *
   * A root node is followed by either
   * - a root/default node of the same strength, or
   * - a root/default node of the next-weaker strength, or
   * - a tailored node of the same strength.
   *
   * A node of a given strength normally implies "common" weights on weaker levels.
   *
   * A node with HAS_BEFORE2 must be immediately followed by
   * a secondary node with an explicit below-common weight, then a secondary tailored node,
   * and later an explicit common-secondary node.
   * The below-common weight can be a root weight,
   * or it can be BEFORE_WEIGHT16 for tailoring before an implied common weight
   * or before the lowest root weight.
   * (&[before 2] resets to an explicit secondary node so that
   * the following addRelation(secondary) tailors right after that.
   * If we did not have this node and instead were to reset on the primary node,
   * then addRelation(secondary) would skip forward to the the COMMON_WEIGHT16 node.)
   *
   * If the flag is not set, then there are no explicit secondary nodes
   * with the common or lower weights.
   *
   * Same for HAS_BEFORE3 for tertiary nodes and weights.
   * A node must not have both flags set.
   *
   * Tailored CEs are initially represented in a CollationDataBuilder as temporary CEs
   * which point to stable indexes in this list,
   * and temporary CEs stored in a CollationDataBuilder only point to tailored nodes.
   *
   * A temporary CE in the ces[] array may point to a non-tailored reset-before-position node,
   * until the next relation is added.
   *
   * At the end, the tailored weights are allocated as necessary,
   * then the tailored nodes are replaced with final CEs,
   * and the CollationData is rewritten by replacing temporary CEs with final ones.
   *
   * We cannot simply insert new nodes in the middle of the array
   * because that would invalidate the indexes stored in existing temporary CEs.
   * We need to use a linked graph with stable indexes to existing nodes.
   * A doubly-linked list seems easiest to maintain.
   *
   * Each node is stored as an int64_t, with its fields stored as bit fields.
   *
   * Root primary node:
   * - primary weight: 32 bits 63..32
   * - reserved/unused/zero: 4 bits 31..28
   *
   * Weaker root nodes & tailored nodes:
   * - a weight: 16 bits 63..48
   *   + a root or default weight for a non-tailored node
   *   + unused/zero for a tailored node
   * - index to the previous node: 20 bits 47..28
   *
   * All types of nodes:
   * - index to the next node: 20 bits 27..8
   *   + nextIndex=0 in last node per root-primary list
   * - reserved/unused/zero bits: bits 7, 4, 2
   * - HAS_BEFORE2: bit 6
   * - HAS_BEFORE3: bit 5
   * - IS_TAILORED: bit 3
   * - the difference strength (primary/secondary/tertiary/quaternary): 2 bits 1..0
   *
   * We could allocate structs with pointers, but we would have to store them
   * in a pointer list so that they can be indexed from temporary CEs,
   * and they would require more memory allocations.
   */
  UVector64 nodes;
404};

406U_NAMESPACE_END}

408#endif  // !UCONFIG_NO_COLLATION
409#endif  // __COLLATIONBUILDER_H__