src/string.cpp

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