source/test/intltest/ucharstrietest.cpp

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