src/string.cpp

   1 /* $Id: string.cpp 26384 2014-03-01 14:14:41Z fonsinchen $ */
   2
   3 /*
   4  * This file is part of OpenTTD.
   5  * OpenTTD is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, version 2.
   6  * OpenTTD is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.
   7  * See the GNU General Public License for more details. You should have received a copy of the GNU General Public License along with OpenTTD. If not, see <http://www.gnu.org/licenses/>.
   8  */
   9
  10 /** @file string.cpp Handling of C-type strings (char*). */
  11
  12 #include "stdafx.h"
  13 #include "debug.h"
  14 #include "core/alloc_func.hpp"
  15 #include "core/math_func.hpp"
  16 #include "string_func.h"
  17 #include "string_base.h"
  18
  19 #include "table/control_codes.h"
  20
  21 #include <stdarg.h>
  22 #include <ctype.h> /* required for tolower() */
  23
  24 #ifdef _MSC_VER
  25 #include <errno.h> // required by vsnprintf implementation for MSVC
  26 #endif
  27
  28 #ifdef WITH_ICU_SORT
  29 /* Required by strnatcmp. */
  30 #include <unicode/ustring.h>
  31 #include "language.h"
  32 #include "gfx_func.h"
  33 #endif /* WITH_ICU_SORT */
  34
  35 /* The function vsnprintf is used internally to perform the required formatting
  36  * tasks. As such this one must be allowed, and makes sure it's terminated. */
  37 #include "safeguards.h"
  38 #undef vsnprintf
  39
  40 /**
  41  * Safer implementation of vsnprintf; same as vsnprintf except:
  42  * - last instead of size, i.e. replace sizeof with lastof.
  43  * - return gives the amount of characters added, not what it would add.
  44  * @param str    buffer to write to up to last
  45  * @param last   last character we may write to
  46  * @param format the formatting (see snprintf)
  47  * @param ap     the list of arguments for the format
  48  * @return the number of added characters
  49  */
  50 int CDECL vseprintf(char *str, const char *last, const char *format, va_list ap)
  51 {
  52         ptrdiff_t diff = last - str;
  53         if (diff < 0) return 0;
  54         return min((int)diff, vsnprintf(str, diff + 1, format, ap));
  55 }
  56
  57 /**
  58  * Appends characters from one string to another.
  59  *
  60  * Appends the source string to the destination string with respect of the
  61  * terminating null-character and and the last pointer to the last element
  62  * in the destination buffer. If the last pointer is set to NULL no
  63  * boundary check is performed.
  64  *
  65  * @note usage: strecat(dst, src, lastof(dst));
  66  * @note lastof() applies only to fixed size arrays
  67  *
  68  * @param dst The buffer containing the target string
  69  * @param src The buffer containing the string to append
  70  * @param last The pointer to the last element of the destination buffer
  71  * @return The pointer to the terminating null-character in the destination buffer
  72  */
  73 char *strecat(char *dst, const char *src, const char *last)
  74 {
  75         assert(dst <= last);
  76         while (*dst != '\0') {
  77                 if (dst == last) return dst;
  78                 dst++;
  79         }
  80
  81         return strecpy(dst, src, last);
  82 }
  83
  84
  85 /**
  86  * Copies characters from one buffer to another.
  87  *
  88  * Copies the source string to the destination buffer with respect of the
  89  * terminating null-character and the last pointer to the last element in
  90  * the destination buffer. If the last pointer is set to NULL no boundary
  91  * check is performed.
  92  *
  93  * @note usage: strecpy(dst, src, lastof(dst));
  94  * @note lastof() applies only to fixed size arrays
  95  *
  96  * @param dst The destination buffer
  97  * @param src The buffer containing the string to copy
  98  * @param last The pointer to the last element of the destination buffer
  99  * @return The pointer to the terminating null-character in the destination buffer
 100  */
 101 char *strecpy(char *dst, const char *src, const char *last)
 102 {
 103         assert(dst <= last);
 104         while (dst != last && *src != '\0') {
 105                 *dst++ = *src++;
 106         }
 107         *dst = '\0';
 108
 109         if (dst == last && *src != '\0') {
 110 #if defined(STRGEN) || defined(SETTINGSGEN)
 111                 error("String too long for destination buffer");
 112 #else /* STRGEN || SETTINGSGEN */
 113                 DEBUG(misc, 0, "String too long for destination buffer");
 114 #endif /* STRGEN || SETTINGSGEN */
 115         }
 116         return dst;
 117 }
 118
 119 /**
 120  * Create a duplicate of the given string.
 121  * @param s    The string to duplicate.
 122  * @param last The last character that is safe to duplicate. If NULL, the whole string is duplicated.
 123  * @note The maximum length of the resulting string might therefore be last - s + 1.
 124  * @return The duplicate of the string.
 125  */
 126 char *stredup(const char *s, const char *last)
 127 {
 128         size_t len = last == NULL ? strlen(s) : ttd_strnlen(s, last - s + 1);
 129         char *tmp = CallocT<char>(len + 1);
 130         memcpy(tmp, s, len);
 131         return tmp;
 132 }
 133
 134 /**
 135  * Format, "printf", into a newly allocated string.
 136  * @param str The formatting string.
 137  * @return The formatted string. You must free this!
 138  */
 139 char *CDECL str_fmt(const char *str, ...)
 140 {
 141         char buf[4096];
 142         va_list va;
 143
 144         va_start(va, str);
 145         int len = vseprintf(buf, lastof(buf), str, va);
 146         va_end(va);
 147         char *p = MallocT<char>(len + 1);
 148         memcpy(p, buf, len + 1);
 149         return p;
 150 }
 151
 152 /**
 153  * Scan the string for old values of SCC_ENCODED and fix it to
 154  * it's new, static value.
 155  * @param str the string to scan
 156  * @param last the last valid character of str
 157  */
 158 void str_fix_scc_encoded(char *str, const char *last)
 159 {
 160         while (str <= last && *str != '\0') {
 161                 size_t len = Utf8EncodedCharLen(*str);
 162                 if ((len == 0 && str + 4 > last) || str + len > last) break;
 163
 164                 WChar c;
 165                 len = Utf8Decode(&c, str);
 166                 if (c == '\0') break;
 167
 168                 if (c == 0xE028 || c == 0xE02A) {
 169                         c = SCC_ENCODED;
 170                 }
 171                 str += Utf8Encode(str, c);
 172         }
 173         *str = '\0';
 174 }
 175
 176
 177 char *str_validate_intl(char *str, const char *last, StringValidationSettings settings)
 178 {
 179         /* Assume the ABSOLUTE WORST to be in str as it comes from the outside. */
 180
 181         char *dst = str;
 182         while (str <= last && *str != '\0') {
 183                 size_t len = Utf8EncodedCharLen(*str);
 184                 /* If the character is unknown, i.e. encoded length is 0
 185                  * we assume worst case for the length check.
 186                  * The length check is needed to prevent Utf8Decode to read
 187                  * over the terminating '\0' if that happens to be placed
 188                  * within the encoding of an UTF8 character. */
 189                 if ((len == 0 && str + 4 > last) || str + len > last) break;
 190
 191                 WChar c;
 192                 len = Utf8Decode(&c, str);
 193                 /* It's possible to encode the string termination character
 194                  * into a multiple bytes. This prevents those termination
 195                  * characters to be skipped */
 196                 if (c == '\0') break;
 197
 198                 if ((IsPrintable(c) && (c < SCC_SPRITE_START || c > SCC_SPRITE_END)) || ((settings & SVS_ALLOW_CONTROL_CODE) != 0 && c == SCC_ENCODED)) {
 199                         /* Copy the character back. Even if dst is current the same as str
 200                          * (i.e. no characters have been changed) this is quicker than
 201                          * moving the pointers ahead by len */
 202                         do {
 203                                 *dst++ = *str++;
 204                         } while (--len != 0);
 205                 } else if ((settings & SVS_ALLOW_NEWLINE) != 0  && c == '\n') {
 206                         *dst++ = *str++;
 207                 } else {
 208                         if ((settings & SVS_ALLOW_NEWLINE) != 0 && c == '\r' && str[1] == '\n') {
 209                                 str += len;
 210                                 continue;
 211                         }
 212                         /* Replace the undesirable character with a question mark */
 213                         str += len;
 214                         if ((settings & SVS_REPLACE_WITH_QUESTION_MARK) != 0) *dst++ = '?';
 215                 }
 216         }
 217
 218         return dst;
 219 }
 220
 221 /**
 222  * Scans the string for valid characters and if it finds invalid ones,
 223  * replaces them with a question mark '?'.
 224  * @param str the string to validate
 225  */
 226 void ValidateString(const char *str)
 227 {
 228         /* We know it is '\0' terminated. */
 229         str_validate(const_cast<char *>(str), str + strlen(str) + 1);
 230 }
 231
 232
 233 /**
 234  * Checks whether the given string is valid, i.e. contains only
 235  * valid (printable) characters and is properly terminated.
 236  * @param str  The string to validate.
 237  * @param last The last character of the string, i.e. the string
 238  *             must be terminated here or earlier.
 239  */
 240 bool StrValid(const char *str, const char *last)
 241 {
 242         /* Assume the ABSOLUTE WORST to be in str as it comes from the outside. */
 243
 244         while (str <= last && *str != '\0') {
 245                 size_t len = Utf8EncodedCharLen(*str);
 246                 /* Encoded length is 0 if the character isn't known.
 247                  * The length check is needed to prevent Utf8Decode to read
 248                  * over the terminating '\0' if that happens to be placed
 249                  * within the encoding of an UTF8 character. */
 250                 if (len == 0 || str + len > last) return false;
 251
 252                 WChar c;
 253                 len = Utf8Decode(&c, str);
 254                 if (!IsPrintable(c) || (c >= SCC_SPRITE_START && c <= SCC_SPRITE_END)) {
 255                         return false;
 256                 }
 257
 258                 str += len;
 259         }
 260
 261         return *str == '\0';
 262 }
 263
 264 /** Scans the string for colour codes and strips them */
 265 void str_strip_colours(char *str)
 266 {
 267         char *dst = str;
 268         WChar c;
 269         size_t len;
 270
 271         for (len = Utf8Decode(&c, str); c != '\0'; len = Utf8Decode(&c, str)) {
 272                 if (c < SCC_BLUE || c > SCC_BLACK) {
 273                         /* Copy the character back. Even if dst is current the same as str
 274                          * (i.e. no characters have been changed) this is quicker than
 275                          * moving the pointers ahead by len */
 276                         do {
 277                                 *dst++ = *str++;
 278                         } while (--len != 0);
 279                 } else {
 280                         /* Just skip (strip) the colour codes */
 281                         str += len;
 282                 }
 283         }
 284         *dst = '\0';
 285 }
 286
 287 /**
 288  * Get the length of an UTF-8 encoded string in number of characters
 289  * and thus not the number of bytes that the encoded string contains.
 290  * @param s The string to get the length for.
 291  * @return The length of the string in characters.
 292  */
 293 size_t Utf8StringLength(const char *s)
 294 {
 295         size_t len = 0;
 296         const char *t = s;
 297         while (Utf8Consume(&t) != 0) len++;
 298         return len;
 299 }
 300
 301
 302 /**
 303  * Convert a given ASCII string to lowercase.
 304  * NOTE: only support ASCII characters, no UTF8 fancy. As currently
 305  * the function is only used to lowercase data-filenames if they are
 306  * not found, this is sufficient. If more, or general functionality is
 307  * needed, look to r7271 where it was removed because it was broken when
 308  * using certain locales: eg in Turkish the uppercase 'I' was converted to
 309  * '?', so just revert to the old functionality
 310  * @param str string to convert
 311  * @return String has changed.
 312  */
 313 bool strtolower(char *str)
 314 {
 315         bool changed = false;
 316         for (; *str != '\0'; str++) {
 317                 char new_str = tolower(*str);
 318                 changed |= new_str != *str;
 319                 *str = new_str;
 320         }
 321         return changed;
 322 }
 323
 324 /**
 325  * Only allow certain keys. You can define the filter to be used. This makes
 326  *  sure no invalid keys can get into an editbox, like BELL.
 327  * @param key character to be checked
 328  * @param afilter the filter to use
 329  * @return true or false depending if the character is printable/valid or not
 330  */
 331 bool IsValidChar(WChar key, CharSetFilter afilter)
 332 {
 333         switch (afilter) {
 334                 case CS_ALPHANUMERAL:  return IsPrintable(key);
 335                 case CS_NUMERAL:       return (key >= '0' && key <= '9');
 336                 case CS_NUMERAL_SPACE: return (key >= '0' && key <= '9') || key == ' ';
 337                 case CS_ALPHA:         return IsPrintable(key) && !(key >= '0' && key <= '9');
 338                 case CS_HEXADECIMAL:   return (key >= '0' && key <= '9') || (key >= 'a' && key <= 'f') || (key >= 'A' && key <= 'F');
 339         }
 340
 341         return false;
 342 }
 343
 344 #ifdef WIN32
 345 #if defined(_MSC_VER) && _MSC_VER < 1900
 346 /**
 347  * Almost POSIX compliant implementation of \c vsnprintf for VC compiler.
 348  * The difference is in the value returned on output truncation. This
 349  * implementation returns size whereas a POSIX implementation returns
 350  * size or more (the number of bytes that would be written to str
 351  * had size been sufficiently large excluding the terminating null byte).
 352  */
 353 int CDECL vsnprintf(char *str, size_t size, const char *format, va_list ap)
 354 {
 355         if (size == 0) return 0;
 356
 357         errno = 0;
 358         int ret = _vsnprintf(str, size, format, ap);
 359
 360         if (ret < 0) {
 361                 if (errno != ERANGE) {
 362                         /* There's a formatting error, better get that looked
 363                          * at properly instead of ignoring it. */
 364                         NOT_REACHED();
 365                 }
 366         } else if ((size_t)ret < size) {
 367                 /* The buffer is big enough for the number of
 368                  * characters stored (excluding null), i.e.
 369                  * the string has been null-terminated. */
 370                 return ret;
 371         }
 372
 373         /* The buffer is too small for _vsnprintf to write the
 374          * null-terminator at its end and return size. */
 375         str[size - 1] = '\0';
 376         return (int)size;
 377 }
 378 #endif /* _MSC_VER */
 379
 380 #endif /* WIN32 */
 381
 382 /**
 383  * Safer implementation of snprintf; same as snprintf except:
 384  * - last instead of size, i.e. replace sizeof with lastof.
 385  * - return gives the amount of characters added, not what it would add.
 386  * @param str    buffer to write to up to last
 387  * @param last   last character we may write to
 388  * @param format the formatting (see snprintf)
 389  * @return the number of added characters
 390  */
 391 int CDECL seprintf(char *str, const char *last, const char *format, ...)
 392 {
 393         va_list ap;
 394
 395         va_start(ap, format);
 396         int ret = vseprintf(str, last, format, ap);
 397         va_end(ap);
 398         return ret;
 399 }
 400
 401
 402 /**
 403  * Convert the md5sum to a hexadecimal string representation
 404  * @param buf buffer to put the md5sum into
 405  * @param last last character of buffer (usually lastof(buf))
 406  * @param md5sum the md5sum itself
 407  * @return a pointer to the next character after the md5sum
 408  */
 409 char *md5sumToString(char *buf, const char *last, const uint8 md5sum[16])
 410 {
 411         char *p = buf;
 412
 413         for (uint i = 0; i < 16; i++) {
 414                 p += seprintf(p, last, "%02X", md5sum[i]);
 415         }
 416
 417         return p;
 418 }
 419
 420
 421 /* UTF-8 handling routines */
 422
 423
 424 /**
 425  * Decode and consume the next UTF-8 encoded character.
 426  * @param c Buffer to place decoded character.
 427  * @param s Character stream to retrieve character from.
 428  * @return Number of characters in the sequence.
 429  */
 430 size_t Utf8Decode(WChar *c, const char *s)
 431 {
 432         assert(c != NULL);
 433
 434         if (!HasBit(s[0], 7)) {
 435                 /* Single byte character: 0xxxxxxx */
 436                 *c = s[0];
 437                 return 1;
 438         } else if (GB(s[0], 5, 3) == 6) {
 439                 if (IsUtf8Part(s[1])) {
 440                         /* Double byte character: 110xxxxx 10xxxxxx */
 441                         *c = GB(s[0], 0, 5) << 6 | GB(s[1], 0, 6);
 442                         if (*c >= 0x80) return 2;
 443                 }
 444         } else if (GB(s[0], 4, 4) == 14) {
 445                 if (IsUtf8Part(s[1]) && IsUtf8Part(s[2])) {
 446                         /* Triple byte character: 1110xxxx 10xxxxxx 10xxxxxx */
 447                         *c = GB(s[0], 0, 4) << 12 | GB(s[1], 0, 6) << 6 | GB(s[2], 0, 6);
 448                         if (*c >= 0x800) return 3;
 449                 }
 450         } else if (GB(s[0], 3, 5) == 30) {
 451                 if (IsUtf8Part(s[1]) && IsUtf8Part(s[2]) && IsUtf8Part(s[3])) {
 452                         /* 4 byte character: 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx */
 453                         *c = GB(s[0], 0, 3) << 18 | GB(s[1], 0, 6) << 12 | GB(s[2], 0, 6) << 6 | GB(s[3], 0, 6);
 454                         if (*c >= 0x10000 && *c <= 0x10FFFF) return 4;
 455                 }
 456         }
 457
 458         /* DEBUG(misc, 1, "[utf8] invalid UTF-8 sequence"); */
 459         *c = '?';
 460         return 1;
 461 }
 462
 463
 464 /**
 465  * Encode a unicode character and place it in the buffer.
 466  * @param buf Buffer to place character.
 467  * @param c   Unicode character to encode.
 468  * @return Number of characters in the encoded sequence.
 469  */
 470 size_t Utf8Encode(char *buf, WChar c)
 471 {
 472         if (c < 0x80) {
 473                 *buf = c;
 474                 return 1;
 475         } else if (c < 0x800) {
 476                 *buf++ = 0xC0 + GB(c,  6, 5);
 477                 *buf   = 0x80 + GB(c,  0, 6);
 478                 return 2;
 479         } else if (c < 0x10000) {
 480                 *buf++ = 0xE0 + GB(c, 12, 4);
 481                 *buf++ = 0x80 + GB(c,  6, 6);
 482                 *buf   = 0x80 + GB(c,  0, 6);
 483                 return 3;
 484         } else if (c < 0x110000) {
 485                 *buf++ = 0xF0 + GB(c, 18, 3);
 486                 *buf++ = 0x80 + GB(c, 12, 6);
 487                 *buf++ = 0x80 + GB(c,  6, 6);
 488                 *buf   = 0x80 + GB(c,  0, 6);
 489                 return 4;
 490         }
 491
 492         /* DEBUG(misc, 1, "[utf8] can't UTF-8 encode value 0x%X", c); */
 493         *buf = '?';
 494         return 1;
 495 }
 496
 497 /**
 498  * Properly terminate an UTF8 string to some maximum length
 499  * @param s string to check if it needs additional trimming
 500  * @param maxlen the maximum length the buffer can have.
 501  * @return the new length in bytes of the string (eg. strlen(new_string))
 502  * @note maxlen is the string length _INCLUDING_ the terminating '\0'
 503  */
 504 size_t Utf8TrimString(char *s, size_t maxlen)
 505 {
 506         size_t length = 0;
 507
 508         for (const char *ptr = strchr(s, '\0'); *s != '\0';) {
 509                 size_t len = Utf8EncodedCharLen(*s);
 510                 /* Silently ignore invalid UTF8 sequences, our only concern trimming */
 511                 if (len == 0) len = 1;
 512
 513                 /* Take care when a hard cutoff was made for the string and
 514                  * the last UTF8 sequence is invalid */
 515                 if (length + len >= maxlen || (s + len > ptr)) break;
 516                 s += len;
 517                 length += len;
 518         }
 519
 520         *s = '\0';
 521         return length;
 522 }
 523
 524 #ifdef DEFINE_STRCASESTR
 525 char *strcasestr(const char *haystack, const char *needle)
 526 {
 527         size_t hay_len = strlen(haystack);
 528         size_t needle_len = strlen(needle);
 529         while (hay_len >= needle_len) {
 530                 if (strncasecmp(haystack, needle, needle_len) == 0) return const_cast<char *>(haystack);
 531
 532                 haystack++;
 533                 hay_len--;
 534         }
 535
 536         return NULL;
 537 }
 538 #endif /* DEFINE_STRCASESTR */
 539
 540 /**
 541  * Skip some of the 'garbage' in the string that we don't want to use
 542  * to sort on. This way the alphabetical sorting will work better as
 543  * we would be actually using those characters instead of some other
 544  * characters such as spaces and tildes at the begin of the name.
 545  * @param str The string to skip the initial garbage of.
 546  * @return The string with the garbage skipped.
 547  */
 548 static const char *SkipGarbage(const char *str)
 549 {
 550         while (*str != '\0' && (*str < '0' || IsInsideMM(*str, ';', '@' + 1) || IsInsideMM(*str, '[', '`' + 1) || IsInsideMM(*str, '{', '~' + 1))) str++;
 551         return str;
 552 }
 553
 554 static int _strnatcmpIntl(const char *s1, const char *s2) {
 555         while (*s1 && *s2) {
 556                 if (IsInsideBS(*s1, '0', 10) && IsInsideBS(*s2, '0', 10)) {
 557                         uint n1 = 0;
 558                         uint n2 = 0;
 559                         for (; IsInsideBS(*s1, '0', 10); s1++) {
 560                                 n1 = (n1 * 10) + (*s1 - '0');
 561                         }
 562                         for (; IsInsideBS(*s2, '0', 10); s2++) {
 563                                 n2 = (n2 * 10) + (*s2 - '0');
 564                         }
 565                         if (n1 != n2) return n1 > n2 ? 1 : -1;
 566                 } else {
 567                         char c1 = tolower(*s1);
 568                         char c2 = tolower(*s2);
 569                         if (c1 != c2) {
 570                                 return c1 > c2 ? 1 : -1;
 571                         }
 572                         s1++;
 573                         s2++;
 574                 }
 575         }
 576         if (*s1 && !*s2) {
 577                 return 1;
 578         } else if (*s2 && !*s1) {
 579                 return -1;
 580         } else {
 581                 return 0;
 582         }
 583 }
 584
 585 /**
 586  * Compares two strings using case insensitive natural sort.
 587  *
 588  * @param s1 First string to compare.
 589  * @param s2 Second string to compare.
 590  * @param ignore_garbage_at_front Skip punctuation characters in the front
 591  * @return Less than zero if s1 < s2, zero if s1 == s2, greater than zero if s1 > s2.
 592  */
 593 int strnatcmp(const char *s1, const char *s2, bool ignore_garbage_at_front)
 594 {
 595         if (ignore_garbage_at_front) {
 596                 s1 = SkipGarbage(s1);
 597                 s2 = SkipGarbage(s2);
 598         }
 599 #ifdef WITH_ICU_SORT
 600         if (_current_collator != NULL) {
 601                 UErrorCode status = U_ZERO_ERROR;
 602                 int result = _current_collator->compareUTF8(s1, s2, status);
 603                 if (U_SUCCESS(status)) return result;
 604         }
 605
 606 #endif /* WITH_ICU_SORT */
 607
 608         /* Do a manual natural sort comparison if ICU is missing or if we cannot create a collator. */
 609         return _strnatcmpIntl(s1, s2);
 610 }
 611
 612 #ifdef WITH_ICU_SORT
 613
 614 #include <unicode/utext.h>
 615 #include <unicode/brkiter.h>
 616
 617 /** String iterator using ICU as a backend. */
 618 class IcuStringIterator : public StringIterator
 619 {
 620         icu::BreakIterator *char_itr; ///< ICU iterator for characters.
 621         icu::BreakIterator *word_itr; ///< ICU iterator for words.
 622
 623         SmallVector<UChar, 32> utf16_str;      ///< UTF-16 copy of the string.
 624         SmallVector<size_t, 32> utf16_to_utf8; ///< Mapping from UTF-16 code point position to index in the UTF-8 source string.
 625
 626 public:
 627         IcuStringIterator() : char_itr(NULL), word_itr(NULL)
 628         {
 629                 UErrorCode status = U_ZERO_ERROR;
 630                 this->char_itr = icu::BreakIterator::createCharacterInstance(icu::Locale(_current_language != NULL ? _current_language->isocode : "en"), status);
 631                 this->word_itr = icu::BreakIterator::createWordInstance(icu::Locale(_current_language != NULL ? _current_language->isocode : "en"), status);
 632
 633                 *this->utf16_str.Append() = '\0';
 634                 *this->utf16_to_utf8.Append() = 0;
 635         }
 636
 637         virtual ~IcuStringIterator()
 638         {
 639                 delete this->char_itr;
 640                 delete this->word_itr;
 641         }
 642
 643         virtual void SetString(const char *s)
 644         {
 645                 const char *string_base = s;
 646
 647                 /* Unfortunately current ICU versions only provide rudimentary support
 648                  * for word break iterators (especially for CJK languages) in combination
 649                  * with UTF-8 input. As a work around we have to convert the input to
 650                  * UTF-16 and create a mapping back to UTF-8 character indices. */
 651                 this->utf16_str.Clear();
 652                 this->utf16_to_utf8.Clear();
 653
 654                 while (*s != '\0') {
 655                         size_t idx = s - string_base;
 656
 657                         WChar c = Utf8Consume(&s);
 658                         if (c < 0x10000) {
 659                                 *this->utf16_str.Append() = (UChar)c;
 660                         } else {
 661                                 /* Make a surrogate pair. */
 662                                 *this->utf16_str.Append() = (UChar)(0xD800 + ((c - 0x10000) >> 10));
 663                                 *this->utf16_str.Append() = (UChar)(0xDC00 + ((c - 0x10000) & 0x3FF));
 664                                 *this->utf16_to_utf8.Append() = idx;
 665                         }
 666                         *this->utf16_to_utf8.Append() = idx;
 667                 }
 668                 *this->utf16_str.Append() = '\0';
 669                 *this->utf16_to_utf8.Append() = s - string_base;
 670
 671                 UText text = UTEXT_INITIALIZER;
 672                 UErrorCode status = U_ZERO_ERROR;
 673                 utext_openUChars(&text, this->utf16_str.Begin(), this->utf16_str.Length() - 1, &status);
 674                 this->char_itr->setText(&text, status);
 675                 this->word_itr->setText(&text, status);
 676                 this->char_itr->first();
 677                 this->word_itr->first();
 678         }
 679
 680         virtual size_t SetCurPosition(size_t pos)
 681         {
 682                 /* Convert incoming position to an UTF-16 string index. */
 683                 uint utf16_pos = 0;
 684                 for (uint i = 0; i < this->utf16_to_utf8.Length(); i++) {
 685                         if (this->utf16_to_utf8[i] == pos) {
 686                                 utf16_pos = i;
 687                                 break;
 688                         }
 689                 }
 690
 691                 /* isBoundary has the documented side-effect of setting the current
 692                  * position to the first valid boundary equal to or greater than
 693                  * the passed value. */
 694                 this->char_itr->isBoundary(utf16_pos);
 695                 return this->utf16_to_utf8[this->char_itr->current()];
 696         }
 697
 698         virtual size_t Next(IterType what)
 699         {
 700                 int32_t pos;
 701                 switch (what) {
 702                         case ITER_CHARACTER:
 703                                 pos = this->char_itr->next();
 704                                 break;
 705
 706                         case ITER_WORD:
 707                                 pos = this->word_itr->following(this->char_itr->current());
 708                                 /* The ICU word iterator considers both the start and the end of a word a valid
 709                                  * break point, but we only want word starts. Move to the next location in
 710                                  * case the new position points to whitespace. */
 711                                 while (pos != icu::BreakIterator::DONE &&
 712                                                 IsWhitespace(Utf16DecodeChar((const uint16 *)&this->utf16_str[pos]))) {
 713                                         int32_t new_pos = this->word_itr->next();
 714                                         /* Don't set it to DONE if it was valid before. Otherwise we'll return END
 715                                          * even though the iterator wasn't at the end of the string before. */
 716                                         if (new_pos == icu::BreakIterator::DONE) break;
 717                                         pos = new_pos;
 718                                 }
 719
 720                                 this->char_itr->isBoundary(pos);
 721                                 break;
 722
 723                         default:
 724                                 NOT_REACHED();
 725                 }
 726
 727                 return pos == icu::BreakIterator::DONE ? END : this->utf16_to_utf8[pos];
 728         }
 729
 730         virtual size_t Prev(IterType what)
 731         {
 732                 int32_t pos;
 733                 switch (what) {
 734                         case ITER_CHARACTER:
 735                                 pos = this->char_itr->previous();
 736                                 break;
 737
 738                         case ITER_WORD:
 739                                 pos = this->word_itr->preceding(this->char_itr->current());
 740                                 /* The ICU word iterator considers both the start and the end of a word a valid
 741                                  * break point, but we only want word starts. Move to the previous location in
 742                                  * case the new position points to whitespace. */
 743                                 while (pos != icu::BreakIterator::DONE &&
 744                                                 IsWhitespace(Utf16DecodeChar((const uint16 *)&this->utf16_str[pos]))) {
 745                                         int32_t new_pos = this->word_itr->previous();
 746                                         /* Don't set it to DONE if it was valid before. Otherwise we'll return END
 747                                          * even though the iterator wasn't at the start of the string before. */
 748                                         if (new_pos == icu::BreakIterator::DONE) break;
 749                                         pos = new_pos;
 750                                 }
 751
 752                                 this->char_itr->isBoundary(pos);
 753                                 break;
 754
 755                         default:
 756                                 NOT_REACHED();
 757                 }
 758
 759                 return pos == icu::BreakIterator::DONE ? END : this->utf16_to_utf8[pos];
 760         }
 761 };
 762
 763 /* static */ StringIterator *StringIterator::Create()
 764 {
 765         return new IcuStringIterator();
 766 }
 767
 768 #else
 769
 770 /** Fallback simple string iterator. */
 771 class DefaultStringIterator : public StringIterator
 772 {
 773         const char *string; ///< Current string.
 774         size_t len;         ///< String length.
 775         size_t cur_pos;     ///< Current iteration position.
 776
 777 public:
 778         DefaultStringIterator() : string(NULL), len(0), cur_pos(0)
 779         {
 780         }
 781
 782         virtual void SetString(const char *s)
 783         {
 784                 this->string = s;
 785                 this->len = strlen(s);
 786                 this->cur_pos = 0;
 787         }
 788
 789         virtual size_t SetCurPosition(size_t pos)
 790         {
 791                 assert(this->string != NULL && pos <= this->len);
 792                 /* Sanitize in case we get a position inside an UTF-8 sequence. */
 793                 while (pos > 0 && IsUtf8Part(this->string[pos])) pos--;
 794                 return this->cur_pos = pos;
 795         }
 796
 797         virtual size_t Next(IterType what)
 798         {
 799                 assert(this->string != NULL);
 800
 801                 /* Already at the end? */
 802                 if (this->cur_pos >= this->len) return END;
 803
 804                 switch (what) {
 805                         case ITER_CHARACTER: {
 806                                 WChar c;
 807                                 this->cur_pos += Utf8Decode(&c, this->string + this->cur_pos);
 808                                 return this->cur_pos;
 809                         }
 810
 811                         case ITER_WORD: {
 812                                 WChar c;
 813                                 /* Consume current word. */
 814                                 size_t offs = Utf8Decode(&c, this->string + this->cur_pos);
 815                                 while (this->cur_pos < this->len && !IsWhitespace(c)) {
 816                                         this->cur_pos += offs;
 817                                         offs = Utf8Decode(&c, this->string + this->cur_pos);
 818                                 }
 819                                 /* Consume whitespace to the next word. */
 820                                 while (this->cur_pos < this->len && IsWhitespace(c)) {
 821                                         this->cur_pos += offs;
 822                                         offs = Utf8Decode(&c, this->string + this->cur_pos);
 823                                 }
 824
 825                                 return this->cur_pos;
 826                         }
 827
 828                         default:
 829                                 NOT_REACHED();
 830                 }
 831
 832                 return END;
 833         }
 834
 835         virtual size_t Prev(IterType what)
 836         {
 837                 assert(this->string != NULL);
 838
 839                 /* Already at the beginning? */
 840                 if (this->cur_pos == 0) return END;
 841
 842                 switch (what) {
 843                         case ITER_CHARACTER:
 844                                 return this->cur_pos = Utf8PrevChar(this->string + this->cur_pos) - this->string;
 845
 846                         case ITER_WORD: {
 847                                 const char *s = this->string + this->cur_pos;
 848                                 WChar c;
 849                                 /* Consume preceding whitespace. */
 850                                 do {
 851                                         s = Utf8PrevChar(s);
 852                                         Utf8Decode(&c, s);
 853                                 } while (s > this->string && IsWhitespace(c));
 854                                 /* Consume preceding word. */
 855                                 while (s > this->string && !IsWhitespace(c)) {
 856                                         s = Utf8PrevChar(s);
 857                                         Utf8Decode(&c, s);
 858                                 }
 859                                 /* Move caret back to the beginning of the word. */
 860                                 if (IsWhitespace(c)) Utf8Consume(&s);
 861
 862                                 return this->cur_pos = s - this->string;
 863                         }
 864
 865                         default:
 866                                 NOT_REACHED();
 867                 }
 868
 869                 return END;
 870         }
 871 };
 872
 873 /* static */ StringIterator *StringIterator::Create()
 874 {
 875         return new DefaultStringIterator();
 876 }
 877
 878 #endif