icuSources/test/intltest/ucharstrietest.cpp

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