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