icuSources/test/intltest/ucharstrietest.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) 2010-2014, International Business Machines
   6 *   Corporation and others.  All Rights Reserved.
   7 *******************************************************************************
   8 *   file name:  ucharstrietest.cpp
   9 *   encoding:   UTF-8
  10 *   tab size:   8 (not used)
  11 *   indentation:4
  12 *
  13 *   created on: 2010nov16
  14 *   created by: Markus W. Scherer
  15 */
  16
  17 #include <string.h>
  18
  19 #include "unicode/utypes.h"
  20 #include "unicode/appendable.h"
  21 #include "unicode/localpointer.h"
  22 #include "unicode/ucharstrie.h"
  23 #include "unicode/ucharstriebuilder.h"
  24 #include "unicode/uniset.h"
  25 #include "unicode/unistr.h"
  26 #include "unicode/utf16.h"
  27 #include "intltest.h"
  28 #include "cmemory.h"
  29
  30 struct StringAndValue {
  31     const char *s;
  32     int32_t value;
  33 };
  34
  35 class UCharsTrieTest : public IntlTest {
  36 public:
  37     UCharsTrieTest();
  38     virtual ~UCharsTrieTest();
  39
  40     void runIndexedTest(int32_t index, UBool exec, const char *&name, char *par=NULL);
  41     void TestBuilder();
  42     void TestEmpty();
  43     void Test_a();
  44     void Test_a_ab();
  45     void TestShortestBranch();
  46     void TestBranches();
  47     void TestLongSequence();
  48     void TestLongBranch();
  49     void TestValuesForState();
  50     void TestCompact();
  51     void TestFirstForCodePoint();
  52     void TestNextForCodePoint();
  53
  54     UCharsTrie *buildLargeTrie(int32_t numUniqueFirst);
  55     void TestLargeTrie();
  56
  57     UCharsTrie *buildMonthsTrie(UStringTrieBuildOption buildOption);
  58     void TestHasUniqueValue();
  59     void TestGetNextUChars();
  60     void TestIteratorFromBranch();
  61     void TestIteratorFromLinearMatch();
  62     void TestTruncatingIteratorFromRoot();
  63     void TestTruncatingIteratorFromLinearMatchShort();
  64     void TestTruncatingIteratorFromLinearMatchLong();
  65     void TestIteratorFromUChars();
  66
  67     void checkData(const StringAndValue data[], int32_t dataLength);
  68     void checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption);
  69     UCharsTrie *buildTrie(const StringAndValue data[], int32_t dataLength,
  70                           UStringTrieBuildOption buildOption);
  71     void checkFirst(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  72     void checkNext(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  73     void checkNextWithState(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  74     void checkNextString(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  75     void checkIterator(UCharsTrie &trie, const StringAndValue data[], int32_t dataLength);
  76     void checkIterator(UCharsTrie::Iterator &iter, const StringAndValue data[], int32_t dataLength);
  77
  78 private:
  79     UCharsTrieBuilder *builder_;
  80 };
  81
  82 extern IntlTest *createUCharsTrieTest() {
  83     return new UCharsTrieTest();
  84 }
  85
  86 UCharsTrieTest::UCharsTrieTest() : builder_(NULL) {
  87     IcuTestErrorCode errorCode(*this, "UCharsTrieTest()");
  88     builder_=new UCharsTrieBuilder(errorCode);
  89 }
  90
  91 UCharsTrieTest::~UCharsTrieTest() {
  92     delete builder_;
  93 }
  94
  95 void UCharsTrieTest::runIndexedTest(int32_t index, UBool exec, const char *&name, char * /*par*/) {
  96     if(exec) {
  97         logln("TestSuite UCharsTrieTest: ");
  98     }
  99     TESTCASE_AUTO_BEGIN;
 100     TESTCASE_AUTO(TestBuilder);
 101     TESTCASE_AUTO(TestEmpty);
 102     TESTCASE_AUTO(Test_a);
 103     TESTCASE_AUTO(Test_a_ab);
 104     TESTCASE_AUTO(TestShortestBranch);
 105     TESTCASE_AUTO(TestBranches);
 106     TESTCASE_AUTO(TestLongSequence);
 107     TESTCASE_AUTO(TestLongBranch);
 108     TESTCASE_AUTO(TestValuesForState);
 109     TESTCASE_AUTO(TestCompact);
 110     TESTCASE_AUTO(TestFirstForCodePoint);
 111     TESTCASE_AUTO(TestNextForCodePoint);
 112     TESTCASE_AUTO(TestLargeTrie);
 113     TESTCASE_AUTO(TestHasUniqueValue);
 114     TESTCASE_AUTO(TestGetNextUChars);
 115     TESTCASE_AUTO(TestIteratorFromBranch);
 116     TESTCASE_AUTO(TestIteratorFromLinearMatch);
 117     TESTCASE_AUTO(TestTruncatingIteratorFromRoot);
 118     TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchShort);
 119     TESTCASE_AUTO(TestTruncatingIteratorFromLinearMatchLong);
 120     TESTCASE_AUTO(TestIteratorFromUChars);
 121     TESTCASE_AUTO_END;
 122 }
 123
 124 void UCharsTrieTest::TestBuilder() {
 125     IcuTestErrorCode errorCode(*this, "TestBuilder()");
 126     delete builder_->build(USTRINGTRIE_BUILD_FAST, errorCode);
 127     if(errorCode.reset()!=U_INDEX_OUTOFBOUNDS_ERROR) {
 128         errln("UCharsTrieBuilder().build() did not set U_INDEX_OUTOFBOUNDS_ERROR");
 129         return;
 130     }
 131     // TODO: remove .build(...) once add() checks for duplicates.
 132     builder_->add("=", 0, errorCode).add("=", 1, errorCode).build(USTRINGTRIE_BUILD_FAST, errorCode);
 133     if(errorCode.reset()!=U_ILLEGAL_ARGUMENT_ERROR) {
 134         errln("UCharsTrieBuilder.add() did not detect duplicates");
 135         return;
 136     }
 137 }
 138
 139 void UCharsTrieTest::TestEmpty() {
 140     static const StringAndValue data[]={
 141         { "", 0 }
 142     };
 143     checkData(data, UPRV_LENGTHOF(data));
 144 }
 145
 146 void UCharsTrieTest::Test_a() {
 147     static const StringAndValue data[]={
 148         { "a", 1 }
 149     };
 150     checkData(data, UPRV_LENGTHOF(data));
 151 }
 152
 153 void UCharsTrieTest::Test_a_ab() {
 154     static const StringAndValue data[]={
 155         { "a", 1 },
 156         { "ab", 100 }
 157     };
 158     checkData(data, UPRV_LENGTHOF(data));
 159 }
 160
 161 void UCharsTrieTest::TestShortestBranch() {
 162     static const StringAndValue data[]={
 163         { "a", 1000 },
 164         { "b", 2000 }
 165     };
 166     checkData(data, UPRV_LENGTHOF(data));
 167 }
 168
 169 void UCharsTrieTest::TestBranches() {
 170     static const StringAndValue data[]={
 171         { "a", 0x10 },
 172         { "cc", 0x40 },
 173         { "e", 0x100 },
 174         { "ggg", 0x400 },
 175         { "i", 0x1000 },
 176         { "kkkk", 0x4000 },
 177         { "n", 0x10000 },
 178         { "ppppp", 0x40000 },
 179         { "r", 0x100000 },
 180         { "sss", 0x200000 },
 181         { "t", 0x400000 },
 182         { "uu", 0x800000 },
 183         { "vv", 0x7fffffff },
 184         { "zz", (int32_t)0x80000000 }
 185     };
 186     for(int32_t length=2; length<=UPRV_LENGTHOF(data); ++length) {
 187         logln("TestBranches length=%d", (int)length);
 188         checkData(data, length);
 189     }
 190 }
 191
 192 void UCharsTrieTest::TestLongSequence() {
 193     static const StringAndValue data[]={
 194         { "a", -1 },
 195         // sequence of linear-match nodes
 196         { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -2 },
 197         // more than 256 units
 198         { "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 199           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 200           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 201           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 202           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"
 203           "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ", -3 }
 204     };
 205     checkData(data, UPRV_LENGTHOF(data));
 206 }
 207
 208 void UCharsTrieTest::TestLongBranch() {
 209     // Split-branch and interesting compact-integer values.
 210     static const StringAndValue data[]={
 211         { "a", -2 },
 212         { "b", -1 },
 213         { "c", 0 },
 214         { "d2", 1 },
 215         { "f", 0x3f },
 216         { "g", 0x40 },
 217         { "h", 0x41 },
 218         { "j23", 0x1900 },
 219         { "j24", 0x19ff },
 220         { "j25", 0x1a00 },
 221         { "k2", 0x1a80 },
 222         { "k3", 0x1aff },
 223         { "l234567890", 0x1b00 },
 224         { "l234567890123", 0x1b01 },
 225         { "nnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnnn", 0x10ffff },
 226         { "oooooooooooooooooooooooooooooooooooooooooooooooooooooo", 0x110000 },
 227         { "pppppppppppppppppppppppppppppppppppppppppppppppppppppp", 0x120000 },
 228         { "r", 0x333333 },
 229         { "s2345", 0x4444444 },
 230         { "t234567890", 0x77777777 },
 231         { "z", (int32_t)0x80000001 }
 232     };
 233     checkData(data, UPRV_LENGTHOF(data));
 234 }
 235
 236 void UCharsTrieTest::TestValuesForState() {
 237     // Check that saveState() and resetToState() interact properly
 238     // with next() and current().
 239     static const StringAndValue data[]={
 240         { "a", -1 },
 241         { "ab", -2 },
 242         { "abc", -3 },
 243         { "abcd", -4 },
 244         { "abcde", -5 },
 245         { "abcdef", -6 }
 246     };
 247     checkData(data, UPRV_LENGTHOF(data));
 248 }
 249
 250 void UCharsTrieTest::TestCompact() {
 251     // Duplicate trailing strings and values provide opportunities for compacting.
 252     static const StringAndValue data[]={
 253         { "+", 0 },
 254         { "+august", 8 },
 255         { "+december", 12 },
 256         { "+july", 7 },
 257         { "+june", 6 },
 258         { "+november", 11 },
 259         { "+october", 10 },
 260         { "+september", 9 },
 261         { "-", 0 },
 262         { "-august", 8 },
 263         { "-december", 12 },
 264         { "-july", 7 },
 265         { "-june", 6 },
 266         { "-november", 11 },
 267         { "-october", 10 },
 268         { "-september", 9 },
 269         // The l+n branch (with its sub-nodes) is a duplicate but will be written
 270         // both times because each time it follows a different linear-match node.
 271         { "xjuly", 7 },
 272         { "xjune", 6 }
 273     };
 274     checkData(data, UPRV_LENGTHOF(data));
 275 }
 276
 277 void UCharsTrieTest::TestFirstForCodePoint() {
 278     static const StringAndValue data[]={
 279         { "a", 1 },
 280         { "a\\ud800", 2 },
 281         { "a\\U00010000", 3 },
 282         { "\\ud840", 4 },
 283         { "\\U00020000\\udbff", 5 },
 284         { "\\U00020000\\U0010ffff", 6 },
 285         { "\\U00020000\\U0010ffffz", 7 },
 286         { "\\U00050000xy", 8 },
 287         { "\\U00050000xyz", 9 }
 288     };
 289     checkData(data, UPRV_LENGTHOF(data));
 290 }
 291
 292 void UCharsTrieTest::TestNextForCodePoint() {
 293     static const StringAndValue data[]={
 294         { "\\u4dff\\U00010000\\u9999\\U00020000\\udfff\\U0010ffff", 2000000000 },
 295         { "\\u4dff\\U00010000\\u9999\\U00020002", 44444 },
 296         { "\\u4dff\\U000103ff", 99999 }
 297     };
 298     LocalPointer<UCharsTrie> trie(buildTrie(data, UPRV_LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 299     if(trie.isNull()) {
 300         return;  // buildTrie() reported an error
 301     }
 302     UStringTrieResult result;
 303     if( (result=trie->nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 304         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 305         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 306         (result=trie->nextForCodePoint(0x20000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 307         (result=trie->nextForCodePoint(0xdfff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 308         (result=trie->nextForCodePoint(0x10ffff))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 309         trie->getValue()!=2000000000
 310     ) {
 311         errln("UCharsTrie.nextForCodePoint() fails for %s", data[0].s);
 312     }
 313     if( (result=trie->firstForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 314         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 315         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 316         (result=trie->nextForCodePoint(0x20002))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 317         trie->getValue()!=44444
 318     ) {
 319         errln("UCharsTrie.nextForCodePoint() fails for %s", data[1].s);
 320     }
 321     if( (result=trie->reset().nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 322         (result=trie->nextForCodePoint(0x10000))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 323         (result=trie->nextForCodePoint(0x9999))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 324         (result=trie->nextForCodePoint(0x20222))!=USTRINGTRIE_NO_MATCH || result!=trie->current()  // no match for trail surrogate
 325     ) {
 326         errln("UCharsTrie.nextForCodePoint() fails for \\u4dff\\U00010000\\u9999\\U00020222");
 327     }
 328     if( (result=trie->reset().nextForCodePoint(0x4dff))!=USTRINGTRIE_NO_VALUE || result!=trie->current() ||
 329         (result=trie->nextForCodePoint(0x103ff))!=USTRINGTRIE_FINAL_VALUE || result!=trie->current() ||
 330         trie->getValue()!=99999
 331     ) {
 332         errln("UCharsTrie.nextForCodePoint() fails for %s", data[2].s);
 333     }
 334 }
 335
 336 // Definitions in the anonymous namespace are invisible outside this file.
 337 namespace {
 338
 339 // Generate (string, value) pairs.
 340 // The first string (before next()) will be empty.
 341 class Generator {
 342 public:
 343     Generator() : value(4711), num(0) {}
 344     void next() {
 345         UChar c;
 346         s.truncate(0);
 347         s.append(c=(UChar)(value>>16));
 348         s.append((UChar)(value>>4));
 349         if(value&1) {
 350             s.append((UChar)value);
 351         }
 352         set.add(c);
 353         value+=((value>>5)&0x7ff)*3+1;
 354         ++num;
 355     }
 356     const UnicodeString &getString() const { return s; }
 357     int32_t getValue() const { return value; }
 358     int32_t countUniqueFirstChars() const { return set.size(); }
 359     int32_t getIndex() const { return num; }
 360
 361 private:
 362     UnicodeString s;
 363     UnicodeSet set;
 364     int32_t value;
 365     int32_t num;
 366 };
 367
 368 }  // end namespace
 369
 370 UCharsTrie *UCharsTrieTest::buildLargeTrie(int32_t numUniqueFirst) {
 371     IcuTestErrorCode errorCode(*this, "buildLargeTrie()");
 372     Generator gen;
 373     builder_->clear();
 374     while(gen.countUniqueFirstChars()<numUniqueFirst) {
 375         builder_->add(gen.getString(), gen.getValue(), errorCode);
 376         gen.next();
 377     }
 378     logln("buildLargeTrie(%ld) added %ld strings", (long)numUniqueFirst, (long)gen.getIndex());
 379     UnicodeString trieUChars;
 380     builder_->buildUnicodeString(USTRINGTRIE_BUILD_FAST, trieUChars, errorCode);
 381     logln("serialized trie size: %ld UChars\n", (long)trieUChars.length());
 382     return new UCharsTrie(trieUChars.getBuffer());
 383 }
 384
 385 // Exercise a large branch node.
 386 void UCharsTrieTest::TestLargeTrie() {
 387     LocalPointer<UCharsTrie> trie(buildLargeTrie(1111));
 388     if(trie.isNull()) {
 389         return;  // buildTrie() reported an error
 390     }
 391     Generator gen;
 392     while(gen.countUniqueFirstChars()<1111) {
 393         UnicodeString x(gen.getString());
 394         int32_t value=gen.getValue();
 395         if(!x.isEmpty()) {
 396             if(trie->first(x[0])==USTRINGTRIE_NO_MATCH) {
 397                 errln("first(first char U+%04X)=USTRINGTRIE_NO_MATCH for string %ld\n",
 398                       x[0], (long)gen.getIndex());
 399                 break;
 400             }
 401             x.remove(0, 1);
 402         }
 403         UStringTrieResult result=trie->next(x.getBuffer(), x.length());
 404         if(!USTRINGTRIE_HAS_VALUE(result) || result!=trie->current() || value!=trie->getValue()) {
 405             errln("next(%d chars U+%04X U+%04X)!=hasValue or "
 406                   "next()!=current() or getValue() wrong "
 407                   "for string %ld\n", (int)x.length(), x[0], x[1], (long)gen.getIndex());
 408             break;
 409         }
 410         gen.next();
 411     }
 412 }
 413
 414 enum {
 415     u_a=0x61,
 416     u_b=0x62,
 417     u_c=0x63,
 418     u_j=0x6a,
 419     u_n=0x6e,
 420     u_r=0x72,
 421     u_u=0x75,
 422     u_y=0x79
 423 };
 424
 425 UCharsTrie *UCharsTrieTest::buildMonthsTrie(UStringTrieBuildOption buildOption) {
 426     // All types of nodes leading to the same value,
 427     // for code coverage of recursive functions.
 428     // In particular, we need a lot of branches on some single level
 429     // to exercise a split-branch node.
 430     static const StringAndValue data[]={
 431         { "august", 8 },
 432         { "jan", 1 },
 433         { "jan.", 1 },
 434         { "jana", 1 },
 435         { "janbb", 1 },
 436         { "janc", 1 },
 437         { "janddd", 1 },
 438         { "janee", 1 },
 439         { "janef", 1 },
 440         { "janf", 1 },
 441         { "jangg", 1 },
 442         { "janh", 1 },
 443         { "janiiii", 1 },
 444         { "janj", 1 },
 445         { "jankk", 1 },
 446         { "jankl", 1 },
 447         { "jankmm", 1 },
 448         { "janl", 1 },
 449         { "janm", 1 },
 450         { "jannnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 },
 451         { "jano", 1 },
 452         { "janpp", 1 },
 453         { "janqqq", 1 },
 454         { "janr", 1 },
 455         { "januar", 1 },
 456         { "january", 1 },
 457         { "july", 7 },
 458         { "jun", 6 },
 459         { "jun.", 6 },
 460         { "june", 6 }
 461     };
 462     return buildTrie(data, UPRV_LENGTHOF(data), buildOption);
 463 }
 464
 465 void UCharsTrieTest::TestHasUniqueValue() {
 466     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 467     if(trie.isNull()) {
 468         return;  // buildTrie() reported an error
 469     }
 470     int32_t uniqueValue;
 471     if(trie->hasUniqueValue(uniqueValue)) {
 472         errln("unique value at root");
 473     }
 474     trie->next(u_j);
 475     trie->next(u_a);
 476     trie->next(u_n);
 477     // hasUniqueValue() directly after next()
 478     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=1) {
 479         errln("not unique value 1 after \"jan\"");
 480     }
 481     trie->first(u_j);
 482     trie->next(u_u);
 483     if(trie->hasUniqueValue(uniqueValue)) {
 484         errln("unique value after \"ju\"");
 485     }
 486     if(trie->next(u_n)!=USTRINGTRIE_INTERMEDIATE_VALUE || 6!=trie->getValue()) {
 487         errln("not normal value 6 after \"jun\"");
 488     }
 489     // hasUniqueValue() after getValue()
 490     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=6) {
 491         errln("not unique value 6 after \"jun\"");
 492     }
 493     // hasUniqueValue() from within a linear-match node
 494     trie->first(u_a);
 495     trie->next(u_u);
 496     if(!trie->hasUniqueValue(uniqueValue) || uniqueValue!=8) {
 497         errln("not unique value 8 after \"au\"");
 498     }
 499 }
 500
 501 void UCharsTrieTest::TestGetNextUChars() {
 502     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL));
 503     if(trie.isNull()) {
 504         return;  // buildTrie() reported an error
 505     }
 506     UnicodeString buffer;
 507     UnicodeStringAppendable app(buffer);
 508     int32_t count=trie->getNextUChars(app);
 509     if(count!=2 || buffer.length()!=2 || buffer[0]!=u_a || buffer[1]!=u_j) {
 510         errln("months getNextUChars()!=[aj] at root");
 511     }
 512     trie->next(u_j);
 513     trie->next(u_a);
 514     trie->next(u_n);
 515     // getNextUChars() directly after next()
 516     buffer.remove();
 517     count=trie->getNextUChars(app);
 518     if(count!=20 || buffer!=UNICODE_STRING_SIMPLE(".abcdefghijklmnopqru")) {
 519         errln("months getNextUChars()!=[.abcdefghijklmnopqru] after \"jan\"");
 520     }
 521     // getNextUChars() after getValue()
 522     trie->getValue();  // next() had returned USTRINGTRIE_INTERMEDIATE_VALUE.
 523     buffer.remove();
 524     count=trie->getNextUChars(app);
 525     if(count!=20 || buffer!=UNICODE_STRING_SIMPLE(".abcdefghijklmnopqru")) {
 526         errln("months getNextUChars()!=[.abcdefghijklmnopqru] after \"jan\"+getValue()");
 527     }
 528     // getNextUChars() from a linear-match node
 529     trie->next(u_u);
 530     buffer.remove();
 531     count=trie->getNextUChars(app);
 532     if(count!=1 || buffer.length()!=1 || buffer[0]!=u_a) {
 533         errln("months getNextUChars()!=[a] after \"janu\"");
 534     }
 535     trie->next(u_a);
 536     buffer.remove();
 537     count=trie->getNextUChars(app);
 538     if(count!=1 || buffer.length()!=1 || buffer[0]!=u_r) {
 539         errln("months getNextUChars()!=[r] after \"janua\"");
 540     }
 541     trie->next(u_r);
 542     trie->next(u_y);
 543     // getNextUChars() after a final match
 544     buffer.remove();
 545     count=trie->getNextUChars(app);
 546     if(count!=0 || buffer.length()!=0) {
 547         errln("months getNextUChars()!=[] after \"january\"");
 548     }
 549 }
 550
 551 void UCharsTrieTest::TestIteratorFromBranch() {
 552     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 553     if(trie.isNull()) {
 554         return;  // buildTrie() reported an error
 555     }
 556     // Go to a branch node.
 557     trie->next(u_j);
 558     trie->next(u_a);
 559     trie->next(u_n);
 560     IcuTestErrorCode errorCode(*this, "TestIteratorFromBranch()");
 561     UCharsTrie::Iterator iter(*trie, 0, errorCode);
 562     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 563         return;
 564     }
 565     // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 566     // following "jan".
 567     static const StringAndValue data[]={
 568         { "", 1 },
 569         { ".", 1 },
 570         { "a", 1 },
 571         { "bb", 1 },
 572         { "c", 1 },
 573         { "ddd", 1 },
 574         { "ee", 1 },
 575         { "ef", 1 },
 576         { "f", 1 },
 577         { "gg", 1 },
 578         { "h", 1 },
 579         { "iiii", 1 },
 580         { "j", 1 },
 581         { "kk", 1 },
 582         { "kl", 1 },
 583         { "kmm", 1 },
 584         { "l", 1 },
 585         { "m", 1 },
 586         { "nnnnnnnnnnnnnnnnnnnnnnnnnnnn", 1 },
 587         { "o", 1 },
 588         { "pp", 1 },
 589         { "qqq", 1 },
 590         { "r", 1 },
 591         { "uar", 1 },
 592         { "uary", 1 }
 593     };
 594     checkIterator(iter, data, UPRV_LENGTHOF(data));
 595     // Reset, and we should get the same result.
 596     logln("after iter.reset()");
 597     checkIterator(iter.reset(), data, UPRV_LENGTHOF(data));
 598 }
 599
 600 void UCharsTrieTest::TestIteratorFromLinearMatch() {
 601     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_SMALL));
 602     if(trie.isNull()) {
 603         return;  // buildTrie() reported an error
 604     }
 605     // Go into a linear-match node.
 606     trie->next(u_j);
 607     trie->next(u_a);
 608     trie->next(u_n);
 609     trie->next(u_u);
 610     trie->next(u_a);
 611     IcuTestErrorCode errorCode(*this, "TestIteratorFromLinearMatch()");
 612     UCharsTrie::Iterator iter(*trie, 0, errorCode);
 613     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 614         return;
 615     }
 616     // Expected data: Same as in buildMonthsTrie(), except only the suffixes
 617     // following "janua".
 618     static const StringAndValue data[]={
 619         { "r", 1 },
 620         { "ry", 1 }
 621     };
 622     checkIterator(iter, data, UPRV_LENGTHOF(data));
 623     // Reset, and we should get the same result.
 624     logln("after iter.reset()");
 625     checkIterator(iter.reset(), data, UPRV_LENGTHOF(data));
 626 }
 627
 628 void UCharsTrieTest::TestTruncatingIteratorFromRoot() {
 629     LocalPointer<UCharsTrie> trie(buildMonthsTrie(USTRINGTRIE_BUILD_FAST));
 630     if(trie.isNull()) {
 631         return;  // buildTrie() reported an error
 632     }
 633     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromRoot()");
 634     UCharsTrie::Iterator iter(*trie, 4, errorCode);
 635     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 636         return;
 637     }
 638     // Expected data: Same as in buildMonthsTrie(), except only the first 4 characters
 639     // of each string, and no string duplicates from the truncation.
 640     static const StringAndValue data[]={
 641         { "augu", -1 },
 642         { "jan", 1 },
 643         { "jan.", 1 },
 644         { "jana", 1 },
 645         { "janb", -1 },
 646         { "janc", 1 },
 647         { "jand", -1 },
 648         { "jane", -1 },
 649         { "janf", 1 },
 650         { "jang", -1 },
 651         { "janh", 1 },
 652         { "jani", -1 },
 653         { "janj", 1 },
 654         { "jank", -1 },
 655         { "janl", 1 },
 656         { "janm", 1 },
 657         { "jann", -1 },
 658         { "jano", 1 },
 659         { "janp", -1 },
 660         { "janq", -1 },
 661         { "janr", 1 },
 662         { "janu", -1 },
 663         { "july", 7 },
 664         { "jun", 6 },
 665         { "jun.", 6 },
 666         { "june", 6 }
 667     };
 668     checkIterator(iter, data, UPRV_LENGTHOF(data));
 669     // Reset, and we should get the same result.
 670     logln("after iter.reset()");
 671     checkIterator(iter.reset(), data, UPRV_LENGTHOF(data));
 672 }
 673
 674 void UCharsTrieTest::TestTruncatingIteratorFromLinearMatchShort() {
 675     static const StringAndValue data[]={
 676         { "abcdef", 10 },
 677         { "abcdepq", 200 },
 678         { "abcdeyz", 3000 }
 679     };
 680     LocalPointer<UCharsTrie> trie(buildTrie(data, UPRV_LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 681     if(trie.isNull()) {
 682         return;  // buildTrie() reported an error
 683     }
 684     // Go into a linear-match node.
 685     trie->next(u_a);
 686     trie->next(u_b);
 687     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchShort()");
 688     // Truncate within the linear-match node.
 689     UCharsTrie::Iterator iter(*trie, 2, errorCode);
 690     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 691         return;
 692     }
 693     static const StringAndValue expected[]={
 694         { "cd", -1 }
 695     };
 696     checkIterator(iter, expected, UPRV_LENGTHOF(expected));
 697     // Reset, and we should get the same result.
 698     logln("after iter.reset()");
 699     checkIterator(iter.reset(), expected, UPRV_LENGTHOF(expected));
 700 }
 701
 702 void UCharsTrieTest::TestTruncatingIteratorFromLinearMatchLong() {
 703     static const StringAndValue data[]={
 704         { "abcdef", 10 },
 705         { "abcdepq", 200 },
 706         { "abcdeyz", 3000 }
 707     };
 708     LocalPointer<UCharsTrie> trie(buildTrie(data, UPRV_LENGTHOF(data), USTRINGTRIE_BUILD_FAST));
 709     if(trie.isNull()) {
 710         return;  // buildTrie() reported an error
 711     }
 712     // Go into a linear-match node.
 713     trie->next(u_a);
 714     trie->next(u_b);
 715     trie->next(u_c);
 716     IcuTestErrorCode errorCode(*this, "TestTruncatingIteratorFromLinearMatchLong()");
 717     // Truncate after the linear-match node.
 718     UCharsTrie::Iterator iter(*trie, 3, errorCode);
 719     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trie) constructor")) {
 720         return;
 721     }
 722     static const StringAndValue expected[]={
 723         { "def", 10 },
 724         { "dep", -1 },
 725         { "dey", -1 }
 726     };
 727     checkIterator(iter, expected, UPRV_LENGTHOF(expected));
 728     // Reset, and we should get the same result.
 729     logln("after iter.reset()");
 730     checkIterator(iter.reset(), expected, UPRV_LENGTHOF(expected));
 731 }
 732
 733 void UCharsTrieTest::TestIteratorFromUChars() {
 734     static const StringAndValue data[]={
 735         { "mm", 3 },
 736         { "mmm", 33 },
 737         { "mmnop", 333 }
 738     };
 739     builder_->clear();
 740     IcuTestErrorCode errorCode(*this, "TestIteratorFromUChars()");
 741     for(int32_t i=0; i<UPRV_LENGTHOF(data); ++i) {
 742         builder_->add(data[i].s, data[i].value, errorCode);
 743     }
 744     UnicodeString trieUChars;
 745     builder_->buildUnicodeString(USTRINGTRIE_BUILD_FAST, trieUChars, errorCode);
 746     UCharsTrie::Iterator iter(trieUChars.getBuffer(), 0, errorCode);
 747     checkIterator(iter, data, UPRV_LENGTHOF(data));
 748 }
 749
 750 void UCharsTrieTest::checkData(const StringAndValue data[], int32_t dataLength) {
 751     logln("checkData(dataLength=%d, fast)", (int)dataLength);
 752     checkData(data, dataLength, USTRINGTRIE_BUILD_FAST);
 753     logln("checkData(dataLength=%d, small)", (int)dataLength);
 754     checkData(data, dataLength, USTRINGTRIE_BUILD_SMALL);
 755 }
 756
 757 void UCharsTrieTest::checkData(const StringAndValue data[], int32_t dataLength, UStringTrieBuildOption buildOption) {
 758     LocalPointer<UCharsTrie> trie(buildTrie(data, dataLength, buildOption));
 759     if(trie.isNull()) {
 760         return;  // buildTrie() reported an error
 761     }
 762     checkFirst(*trie, data, dataLength);
 763     checkNext(*trie, data, dataLength);
 764     checkNextWithState(*trie, data, dataLength);
 765     checkNextString(*trie, data, dataLength);
 766     checkIterator(*trie, data, dataLength);
 767 }
 768
 769 UCharsTrie *UCharsTrieTest::buildTrie(const StringAndValue data[], int32_t dataLength,
 770                                       UStringTrieBuildOption buildOption) {
 771     IcuTestErrorCode errorCode(*this, "buildTrie()");
 772     // Add the items to the trie builder in an interesting (not trivial, not random) order.
 773     int32_t index, step;
 774     if(dataLength&1) {
 775         // Odd number of items.
 776         index=dataLength/2;
 777         step=2;
 778     } else if((dataLength%3)!=0) {
 779         // Not a multiple of 3.
 780         index=dataLength/5;
 781         step=3;
 782     } else {
 783         index=dataLength-1;
 784         step=-1;
 785     }
 786     builder_->clear();
 787     for(int32_t i=0; i<dataLength; ++i) {
 788         builder_->add(UnicodeString(data[index].s, -1, US_INV).unescape(),
 789                       data[index].value, errorCode);
 790         index=(index+step)%dataLength;
 791     }
 792     UnicodeString trieUChars;
 793     builder_->buildUnicodeString(buildOption, trieUChars, errorCode);
 794     LocalPointer<UCharsTrie> trie(builder_->build(buildOption, errorCode));
 795     if(!errorCode.errIfFailureAndReset("add()/build()")) {
 796         builder_->add("zzz", 999, errorCode);
 797         if(errorCode.reset()!=U_NO_WRITE_PERMISSION) {
 798             errln("builder.build().add(zzz) did not set U_NO_WRITE_PERMISSION");
 799         }
 800     }
 801     logln("serialized trie size: %ld UChars\n", (long)trieUChars.length());
 802     UnicodeString trieUChars2;
 803     builder_->buildUnicodeString(buildOption, trieUChars2, errorCode);
 804     if(trieUChars.getBuffer()==trieUChars2.getBuffer()) {
 805         errln("builder.buildUnicodeString() before & after build() returned same array");
 806     }
 807     if(errorCode.isFailure()) {
 808         return NULL;
 809     }
 810     // Tries from either build() method should be identical but
 811     // UCharsTrie does not implement equals().
 812     // We just return either one.
 813     if((dataLength&1)!=0) {
 814         return trie.orphan();
 815     } else {
 816         return new UCharsTrie(trieUChars2.getBuffer());
 817     }
 818 }
 819
 820 void UCharsTrieTest::checkFirst(UCharsTrie &trie,
 821                                 const StringAndValue data[], int32_t dataLength) {
 822     for(int32_t i=0; i<dataLength; ++i) {
 823         if(*data[i].s==0) {
 824             continue;  // skip empty string
 825         }
 826         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 827         UChar32 c=expectedString[0];
 828         UChar32 nextCp=expectedString.length()>1 ? expectedString[1] : 0;
 829         UStringTrieResult firstResult=trie.first(c);
 830         int32_t firstValue=USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1;
 831         UStringTrieResult nextResult=trie.next(nextCp);
 832         if(firstResult!=trie.reset().next(c) ||
 833            firstResult!=trie.current() ||
 834            firstValue!=(USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1) ||
 835            nextResult!=trie.next(nextCp)
 836         ) {
 837             errln("trie.first(U+%04X)!=trie.reset().next(same) for %s",
 838                   c, data[i].s);
 839         }
 840         c=expectedString.char32At(0);
 841         int32_t cLength=U16_LENGTH(c);
 842         nextCp=expectedString.length()>cLength ? expectedString.char32At(cLength) : 0;
 843         firstResult=trie.firstForCodePoint(c);
 844         firstValue=USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1;
 845         nextResult=trie.nextForCodePoint(nextCp);
 846         if(firstResult!=trie.reset().nextForCodePoint(c) ||
 847            firstResult!=trie.current() ||
 848            firstValue!=(USTRINGTRIE_HAS_VALUE(firstResult) ? trie.getValue() : -1) ||
 849            nextResult!=trie.nextForCodePoint(nextCp)
 850         ) {
 851             errln("trie.firstForCodePoint(U+%04X)!=trie.reset().nextForCodePoint(same) for %s",
 852                   c, data[i].s);
 853         }
 854     }
 855     trie.reset();
 856 }
 857
 858 void UCharsTrieTest::checkNext(UCharsTrie &trie,
 859                                const StringAndValue data[], int32_t dataLength) {
 860     UCharsTrie::State state;
 861     for(int32_t i=0; i<dataLength; ++i) {
 862         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 863         int32_t stringLength= (i&1) ? -1 : expectedString.length();
 864         UStringTrieResult result;
 865         if( !USTRINGTRIE_HAS_VALUE(
 866                 result=trie.next(expectedString.getTerminatedBuffer(), stringLength)) ||
 867             result!=trie.current()
 868         ) {
 869             errln("trie does not seem to contain %s", data[i].s);
 870         } else if(trie.getValue()!=data[i].value) {
 871             errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx",
 872                   data[i].s,
 873                   (long)trie.getValue(), (long)trie.getValue(),
 874                   (long)data[i].value, (long)data[i].value);
 875         } else if(result!=trie.current() || trie.getValue()!=data[i].value) {
 876             errln("trie value for %s changes when repeating current()/getValue()", data[i].s);
 877         }
 878         trie.reset();
 879         stringLength=expectedString.length();
 880         result=trie.current();
 881         for(int32_t j=0; j<stringLength; ++j) {
 882             if(!USTRINGTRIE_HAS_NEXT(result)) {
 883                 errln("trie.current()!=hasNext before end of %s (at index %d)", data[i].s, j);
 884                 break;
 885             }
 886             if(result==USTRINGTRIE_INTERMEDIATE_VALUE) {
 887                 trie.getValue();
 888                 if(trie.current()!=USTRINGTRIE_INTERMEDIATE_VALUE) {
 889                     errln("trie.getValue().current()!=USTRINGTRIE_INTERMEDIATE_VALUE before end of %s (at index %d)", data[i].s, j);
 890                     break;
 891                 }
 892             }
 893             result=trie.next(expectedString[j]);
 894             if(!USTRINGTRIE_MATCHES(result)) {
 895                 errln("trie.next()=USTRINGTRIE_NO_MATCH before end of %s (at index %d)", data[i].s, j);
 896                 break;
 897             }
 898             if(result!=trie.current()) {
 899                 errln("trie.next()!=following current() before end of %s (at index %d)", data[i].s, j);
 900                 break;
 901             }
 902         }
 903         if(!USTRINGTRIE_HAS_VALUE(result)) {
 904             errln("trie.next()!=hasValue at the end of %s", data[i].s);
 905             continue;
 906         }
 907         trie.getValue();
 908         if(result!=trie.current()) {
 909             errln("trie.current() != current()+getValue()+current() after end of %s",
 910                   data[i].s);
 911         }
 912         // Compare the final current() with whether next() can actually continue.
 913         trie.saveState(state);
 914         UBool nextContinues=FALSE;
 915         for(int32_t c=0x20; c<0xe000; ++c) {
 916             if(c==0x80) {
 917                 c=0xd800;  // Check for ASCII and surrogates but not all of the BMP.
 918             }
 919             if(trie.resetToState(state).next(c)) {
 920                 nextContinues=TRUE;
 921                 break;
 922             }
 923         }
 924         if((result==USTRINGTRIE_INTERMEDIATE_VALUE)!=nextContinues) {
 925             errln("(trie.current()==USTRINGTRIE_INTERMEDIATE_VALUE) contradicts "
 926                   "(trie.next(some UChar)!=USTRINGTRIE_NO_MATCH) after end of %s", data[i].s);
 927         }
 928         trie.reset();
 929     }
 930 }
 931
 932 void UCharsTrieTest::checkNextWithState(UCharsTrie &trie,
 933                                         const StringAndValue data[], int32_t dataLength) {
 934     UCharsTrie::State noState, state;
 935     for(int32_t i=0; i<dataLength; ++i) {
 936         if((i&1)==0) {
 937             // This should have no effect.
 938             trie.resetToState(noState);
 939         }
 940         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 941         int32_t stringLength=expectedString.length();
 942         int32_t partialLength=stringLength/3;
 943         for(int32_t j=0; j<partialLength; ++j) {
 944             if(!USTRINGTRIE_MATCHES(trie.next(expectedString[j]))) {
 945                 errln("trie.next()=USTRINGTRIE_NO_MATCH for a prefix of %s", data[i].s);
 946                 return;
 947             }
 948         }
 949         trie.saveState(state);
 950         UStringTrieResult resultAtState=trie.current();
 951         UStringTrieResult result;
 952         int32_t valueAtState=-99;
 953         if(USTRINGTRIE_HAS_VALUE(resultAtState)) {
 954             valueAtState=trie.getValue();
 955         }
 956         result=trie.next(0);  // mismatch
 957         if(result!=USTRINGTRIE_NO_MATCH || result!=trie.current()) {
 958             errln("trie.next(0) matched after part of %s", data[i].s);
 959         }
 960         if( resultAtState!=trie.resetToState(state).current() ||
 961             (USTRINGTRIE_HAS_VALUE(resultAtState) && valueAtState!=trie.getValue())
 962         ) {
 963             errln("trie.next(part of %s) changes current()/getValue() after "
 964                   "saveState/next(0)/resetToState",
 965                   data[i].s);
 966         } else if(!USTRINGTRIE_HAS_VALUE(
 967                       result=trie.next(expectedString.getTerminatedBuffer()+partialLength,
 968                                        stringLength-partialLength)) ||
 969                   result!=trie.current()) {
 970             errln("trie.next(rest of %s) does not seem to contain %s after "
 971                   "saveState/next(0)/resetToState",
 972                   data[i].s, data[i].s);
 973         } else if(!USTRINGTRIE_HAS_VALUE(
 974                       result=trie.resetToState(state).
 975                                   next(expectedString.getTerminatedBuffer()+partialLength,
 976                                        stringLength-partialLength)) ||
 977                   result!=trie.current()) {
 978             errln("trie does not seem to contain %s after saveState/next(rest)/resetToState",
 979                   data[i].s);
 980         } else if(trie.getValue()!=data[i].value) {
 981             errln("trie value for %s is %ld=0x%lx instead of expected %ld=0x%lx",
 982                   data[i].s,
 983                   (long)trie.getValue(), (long)trie.getValue(),
 984                   (long)data[i].value, (long)data[i].value);
 985         }
 986         trie.reset();
 987     }
 988 }
 989
 990 // next(string) is also tested in other functions,
 991 // but here we try to go partway through the string, and then beyond it.
 992 void UCharsTrieTest::checkNextString(UCharsTrie &trie,
 993                                      const StringAndValue data[], int32_t dataLength) {
 994     for(int32_t i=0; i<dataLength; ++i) {
 995         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
 996         int32_t stringLength=expectedString.length();
 997         if(!trie.next(expectedString.getTerminatedBuffer(), stringLength/2)) {
 998             errln("trie.next(up to middle of string)=USTRINGTRIE_NO_MATCH for %s", data[i].s);
 999             continue;
1000         }
1001         // Test that we stop properly at the end of the string.
1002         if(trie.next(expectedString.getTerminatedBuffer()+stringLength/2,
1003                      stringLength+1-stringLength/2)) {
1004             errln("trie.next(string+NUL)!=USTRINGTRIE_NO_MATCH for %s", data[i].s);
1005         }
1006         trie.reset();
1007     }
1008 }
1009
1010 void UCharsTrieTest::checkIterator(UCharsTrie &trie,
1011                                    const StringAndValue data[], int32_t dataLength) {
1012     IcuTestErrorCode errorCode(*this, "checkIterator()");
1013     UCharsTrie::Iterator iter(trie, 0, errorCode);
1014     if(errorCode.errIfFailureAndReset("UCharsTrie::Iterator(trieUChars) constructor")) {
1015         return;
1016     }
1017     checkIterator(iter, data, dataLength);
1018 }
1019
1020 void UCharsTrieTest::checkIterator(UCharsTrie::Iterator &iter,
1021                                    const StringAndValue data[], int32_t dataLength) {
1022     IcuTestErrorCode errorCode(*this, "checkIterator()");
1023     for(int32_t i=0; i<dataLength; ++i) {
1024         if(!iter.hasNext()) {
1025             errln("trie iterator hasNext()=FALSE for item %d: %s", (int)i, data[i].s);
1026             break;
1027         }
1028         UBool hasNext=iter.next(errorCode);
1029         if(errorCode.errIfFailureAndReset("trie iterator next() for item %d: %s", (int)i, data[i].s)) {
1030             break;
1031         }
1032         if(!hasNext) {
1033             errln("trie iterator next()=FALSE for item %d: %s", (int)i, data[i].s);
1034             break;
1035         }
1036         UnicodeString expectedString=UnicodeString(data[i].s, -1, US_INV).unescape();
1037         if(iter.getString()!=expectedString) {
1038             char buffer[1000];
1039             UnicodeString invString(prettify(iter.getString()));
1040             invString.extract(0, invString.length(), buffer, UPRV_LENGTHOF(buffer), US_INV);
1041             errln("trie iterator next().getString()=%s but expected %s for item %d",
1042                   buffer, data[i].s, (int)i);
1043         }
1044         if(iter.getValue()!=data[i].value) {
1045             errln("trie iterator next().getValue()=%ld=0x%lx but expected %ld=0x%lx for item %d: %s",
1046                   (long)iter.getValue(), (long)iter.getValue(),
1047                   (long)data[i].value, (long)data[i].value,
1048                   (int)i, data[i].s);
1049         }
1050     }
1051     if(iter.hasNext()) {
1052         errln("trie iterator hasNext()=TRUE after all items");
1053     }
1054     UBool hasNext=iter.next(errorCode);
1055     errorCode.errIfFailureAndReset("trie iterator next() after all items");
1056     if(hasNext) {
1057         errln("trie iterator next()=TRUE after all items");
1058     }
1059 }