glib/gunicollate.c

   1 /* gunicollate.c - Collation
   2  *
   3  *  Copyright 2001,2005 Red Hat, Inc.
   4  *
   5  * This library is free software; you can redistribute it and/or
   6  * modify it under the terms of the GNU Lesser General Public
   7  * License as published by the Free Software Foundation; either
   8  * version 2 of the License, or (at your option) any later version.
   9  *
  10  * This library is distributed in the hope that it will be useful,
  11  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  12  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  13  * Lesser General Public License for more details.
  14  *
  15  * You should have received a copy of the GNU Lesser General Public License
  16  * along with this library; if not, see <http://www.gnu.org/licenses/>.
  17  */
  18
  19 #include "config.h"
  20
  21 #include <locale.h>
  22 #include <string.h>
  23 #ifdef __STDC_ISO_10646__
  24 #include <wchar.h>
  25 #endif
  26
  27 #ifdef HAVE_CARBON
  28 #include <CoreServices/CoreServices.h>
  29 #endif
  30
  31 #include "gmem.h"
  32 #include "gunicode.h"
  33 #include "gunicodeprivate.h"
  34 #include "gstring.h"
  35 #include "gstrfuncs.h"
  36 #include "gtestutils.h"
  37 #include "gcharset.h"
  38 #ifndef __STDC_ISO_10646__
  39 #include "gconvert.h"
  40 #endif
  41
  42
  43 #ifdef _MSC_VER
  44 /* Workaround for bug in MSVCR80.DLL */
  45 static gsize
  46 msc_strxfrm_wrapper (char       *string1,
  47                      const char *string2,
  48                      gsize       count)
  49 {
  50   if (!string1 || count <= 0)
  51     {
  52       char tmp;
  53
  54       return strxfrm (&tmp, string2, 1);
  55     }
  56   return strxfrm (string1, string2, count);
  57 }
  58 #define strxfrm msc_strxfrm_wrapper
  59 #endif
  60
  61 /**
  62  * g_utf8_collate:
  63  * @str1: a UTF-8 encoded string
  64  * @str2: a UTF-8 encoded string
  65  *
  66  * Compares two strings for ordering using the linguistically
  67  * correct rules for the [current locale][setlocale].
  68  * When sorting a large number of strings, it will be significantly
  69  * faster to obtain collation keys with g_utf8_collate_key() and
  70  * compare the keys with strcmp() when sorting instead of sorting
  71  * the original strings.
  72  *
  73  * Returns: < 0 if @str1 compares before @str2,
  74  *   0 if they compare equal, > 0 if @str1 compares after @str2.
  75  **/
  76 gint
  77 g_utf8_collate (const gchar *str1,
  78                 const gchar *str2)
  79 {
  80   gint result;
  81
  82 #ifdef HAVE_CARBON
  83
  84   UniChar *str1_utf16;
  85   UniChar *str2_utf16;
  86   glong len1;
  87   glong len2;
  88   SInt32 retval = 0;
  89
  90   g_return_val_if_fail (str1 != NULL, 0);
  91   g_return_val_if_fail (str2 != NULL, 0);
  92
  93   str1_utf16 = g_utf8_to_utf16 (str1, -1, NULL, &len1, NULL);
  94   str2_utf16 = g_utf8_to_utf16 (str2, -1, NULL, &len2, NULL);
  95
  96   UCCompareTextDefault (kUCCollateStandardOptions,
  97                         str1_utf16, len1, str2_utf16, len2,
  98                         NULL, &retval);
  99   result = retval;
 100
 101   g_free (str2_utf16);
 102   g_free (str1_utf16);
 103
 104 #elif defined(__STDC_ISO_10646__)
 105
 106   gunichar *str1_norm;
 107   gunichar *str2_norm;
 108
 109   g_return_val_if_fail (str1 != NULL, 0);
 110   g_return_val_if_fail (str2 != NULL, 0);
 111
 112   str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);
 113   str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);
 114
 115   result = wcscoll ((wchar_t *)str1_norm, (wchar_t *)str2_norm);
 116
 117   g_free (str1_norm);
 118   g_free (str2_norm);
 119
 120 #else /* !__STDC_ISO_10646__ */
 121
 122   const gchar *charset;
 123   gchar *str1_norm;
 124   gchar *str2_norm;
 125
 126   g_return_val_if_fail (str1 != NULL, 0);
 127   g_return_val_if_fail (str2 != NULL, 0);
 128
 129   str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);
 130   str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);
 131
 132   if (g_get_charset (&charset))
 133     {
 134       result = strcoll (str1_norm, str2_norm);
 135     }
 136   else
 137     {
 138       gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
 139       gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
 140
 141       if (str1_locale && str2_locale)
 142         result =  strcoll (str1_locale, str2_locale);
 143       else if (str1_locale)
 144         result = -1;
 145       else if (str2_locale)
 146         result = 1;
 147       else
 148         result = strcmp (str1_norm, str2_norm);
 149
 150       g_free (str1_locale);
 151       g_free (str2_locale);
 152     }
 153
 154   g_free (str1_norm);
 155   g_free (str2_norm);
 156
 157 #endif /* __STDC_ISO_10646__ */
 158
 159   return result;
 160 }
 161
 162 #if defined(__STDC_ISO_10646__) || defined(HAVE_CARBON)
 163 /* We need UTF-8 encoding of numbers to encode the weights if
 164  * we are using wcsxfrm. However, we aren't encoding Unicode
 165  * characters, so we can't simply use g_unichar_to_utf8.
 166  *
 167  * The following routine is taken (with modification) from GNU
 168  * libc's strxfrm routine:
 169  *
 170  * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.
 171  * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.
 172  */
 173 static inline int
 174 utf8_encode (char *buf, wchar_t val)
 175 {
 176   int retval;
 177
 178   if (val < 0x80)
 179     {
 180       if (buf)
 181         *buf++ = (char) val;
 182       retval = 1;
 183     }
 184   else
 185     {
 186       int step;
 187
 188       for (step = 2; step < 6; ++step)
 189         if ((val & (~(guint32)0 << (5 * step + 1))) == 0)
 190           break;
 191       retval = step;
 192
 193       if (buf)
 194         {
 195           *buf = (unsigned char) (~0xff >> step);
 196           --step;
 197           do
 198             {
 199               buf[step] = 0x80 | (val & 0x3f);
 200               val >>= 6;
 201             }
 202           while (--step > 0);
 203           *buf |= val;
 204         }
 205     }
 206
 207   return retval;
 208 }
 209 #endif /* __STDC_ISO_10646__ || HAVE_CARBON */
 210
 211 #ifdef HAVE_CARBON
 212
 213 static gchar *
 214 collate_key_to_string (UCCollationValue *key,
 215                        gsize             key_len)
 216 {
 217   gchar *result;
 218   gsize result_len = 0;
 219   const gsize start = 2 * sizeof (void *) / sizeof (UCCollationValue);
 220   gsize i;
 221
 222   /* The first codes should be skipped: the same string on the same
 223    * system can get different values at runtime in those positions,
 224    * and they do not sort correctly.  The exact size of the prefix
 225    * depends on whether we are building 64 or 32 bit.
 226    */
 227   if (key_len <= start)
 228     return g_strdup ("");
 229
 230   for (i = start; i < key_len; i++)
 231     result_len += utf8_encode (NULL, g_htonl (key[i] + 1));
 232
 233   result = g_malloc (result_len + 1);
 234   result_len = 0;
 235   for (i = start; i < key_len; i++)
 236     result_len += utf8_encode (result + result_len, g_htonl (key[i] + 1));
 237
 238   result[result_len] = '\0';
 239
 240   return result;
 241 }
 242
 243 static gchar *
 244 carbon_collate_key_with_collator (const gchar *str,
 245                                   gssize       len,
 246                                   CollatorRef  collator)
 247 {
 248   UniChar *str_utf16 = NULL;
 249   glong len_utf16;
 250   OSStatus ret;
 251   UCCollationValue staticbuf[512];
 252   UCCollationValue *freeme = NULL;
 253   UCCollationValue *buf;
 254   ItemCount buf_len;
 255   ItemCount key_len;
 256   ItemCount try_len;
 257   gchar *result = NULL;
 258
 259   str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);
 260   try_len = len_utf16 * 5 + 2;
 261
 262   if (try_len <= sizeof staticbuf)
 263     {
 264       buf = staticbuf;
 265       buf_len = sizeof staticbuf;
 266     }
 267   else
 268     {
 269       freeme = g_new (UCCollationValue, try_len);
 270       buf = freeme;
 271       buf_len = try_len;
 272     }
 273
 274   ret = UCGetCollationKey (collator, str_utf16, len_utf16,
 275                            buf_len, &key_len, buf);
 276
 277   if (ret == kCollateBufferTooSmall)
 278     {
 279       freeme = g_renew (UCCollationValue, freeme, try_len * 2);
 280       buf = freeme;
 281       buf_len = try_len * 2;
 282       ret = UCGetCollationKey (collator, str_utf16, len_utf16,
 283                                buf_len, &key_len, buf);
 284     }
 285
 286   if (ret == 0)
 287     result = collate_key_to_string (buf, key_len);
 288   else
 289     result = g_strdup ("");
 290
 291   g_free (freeme);
 292   g_free (str_utf16);
 293   return result;
 294 }
 295
 296 static gchar *
 297 carbon_collate_key (const gchar *str,
 298                     gssize       len)
 299 {
 300   static CollatorRef collator;
 301
 302   if (G_UNLIKELY (!collator))
 303     {
 304       UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);
 305
 306       if (!collator)
 307         {
 308           static gboolean been_here;
 309           if (!been_here)
 310             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
 311           been_here = TRUE;
 312           return g_strdup ("");
 313         }
 314     }
 315
 316   return carbon_collate_key_with_collator (str, len, collator);
 317 }
 318
 319 static gchar *
 320 carbon_collate_key_for_filename (const gchar *str,
 321                                  gssize       len)
 322 {
 323   static CollatorRef collator;
 324
 325   if (G_UNLIKELY (!collator))
 326     {
 327       /* http://developer.apple.com/qa/qa2004/qa1159.html */
 328       UCCreateCollator (NULL, 0,
 329                         kUCCollateComposeInsensitiveMask
 330                          | kUCCollateWidthInsensitiveMask
 331                          | kUCCollateCaseInsensitiveMask
 332                          | kUCCollateDigitsOverrideMask
 333                          | kUCCollateDigitsAsNumberMask
 334                          | kUCCollatePunctuationSignificantMask,
 335                         &collator);
 336
 337       if (!collator)
 338         {
 339           static gboolean been_here;
 340           if (!been_here)
 341             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
 342           been_here = TRUE;
 343           return g_strdup ("");
 344         }
 345     }
 346
 347   return carbon_collate_key_with_collator (str, len, collator);
 348 }
 349
 350 #endif /* HAVE_CARBON */
 351
 352 /**
 353  * g_utf8_collate_key:
 354  * @str: a UTF-8 encoded string.
 355  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 356  *
 357  * Converts a string into a collation key that can be compared
 358  * with other collation keys produced by the same function using
 359  * strcmp().
 360  *
 361  * The results of comparing the collation keys of two strings
 362  * with strcmp() will always be the same as comparing the two
 363  * original keys with g_utf8_collate().
 364  *
 365  * Note that this function depends on the [current locale][setlocale].
 366  *
 367  * Returns: a newly allocated string. This string should
 368  *   be freed with g_free() when you are done with it.
 369  **/
 370 gchar *
 371 g_utf8_collate_key (const gchar *str,
 372                     gssize       len)
 373 {
 374   gchar *result;
 375
 376 #ifdef HAVE_CARBON
 377
 378   g_return_val_if_fail (str != NULL, NULL);
 379   result = carbon_collate_key (str, len);
 380
 381 #elif defined(__STDC_ISO_10646__)
 382
 383   gsize xfrm_len;
 384   gunichar *str_norm;
 385   wchar_t *result_wc;
 386   gsize i;
 387   gsize result_len = 0;
 388
 389   g_return_val_if_fail (str != NULL, NULL);
 390
 391   str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);
 392
 393   xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
 394   result_wc = g_new (wchar_t, xfrm_len + 1);
 395   wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);
 396
 397   for (i = 0; i < xfrm_len; i++)
 398     result_len += utf8_encode (NULL, result_wc[i]);
 399
 400   result = g_malloc (result_len + 1);
 401   result_len = 0;
 402   for (i = 0; i < xfrm_len; i++)
 403     result_len += utf8_encode (result + result_len, result_wc[i]);
 404
 405   result[result_len] = '\0';
 406
 407   g_free (result_wc);
 408   g_free (str_norm);
 409
 410   return result;
 411 #else /* !__STDC_ISO_10646__ */
 412
 413   gsize xfrm_len;
 414   const gchar *charset;
 415   gchar *str_norm;
 416
 417   g_return_val_if_fail (str != NULL, NULL);
 418
 419   str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);
 420
 421   result = NULL;
 422
 423   if (g_get_charset (&charset))
 424     {
 425       xfrm_len = strxfrm (NULL, str_norm, 0);
 426       if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
 427         {
 428           result = g_malloc (xfrm_len + 1);
 429           strxfrm (result, str_norm, xfrm_len + 1);
 430         }
 431     }
 432   else
 433     {
 434       gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
 435
 436       if (str_locale)
 437         {
 438           xfrm_len = strxfrm (NULL, str_locale, 0);
 439           if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
 440             {
 441               g_free (str_locale);
 442               str_locale = NULL;
 443             }
 444         }
 445       if (str_locale)
 446         {
 447           result = g_malloc (xfrm_len + 2);
 448           result[0] = 'A';
 449           strxfrm (result + 1, str_locale, xfrm_len + 1);
 450
 451           g_free (str_locale);
 452         }
 453     }
 454
 455   if (!result)
 456     {
 457       xfrm_len = strlen (str_norm);
 458       result = g_malloc (xfrm_len + 2);
 459       result[0] = 'B';
 460       memcpy (result + 1, str_norm, xfrm_len);
 461       result[xfrm_len+1] = '\0';
 462     }
 463
 464   g_free (str_norm);
 465 #endif /* __STDC_ISO_10646__ */
 466
 467   return result;
 468 }
 469
 470 /* This is a collation key that is very very likely to sort before any
 471  * collation key that libc strxfrm generates. We use this before any
 472  * special case (dot or number) to make sure that its sorted before
 473  * anything else.
 474  */
 475 #define COLLATION_SENTINEL "\1\1\1"
 476
 477 /**
 478  * g_utf8_collate_key_for_filename:
 479  * @str: a UTF-8 encoded string.
 480  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
 481  *
 482  * Converts a string into a collation key that can be compared
 483  * with other collation keys produced by the same function using strcmp().
 484  *
 485  * In order to sort filenames correctly, this function treats the dot '.'
 486  * as a special case. Most dictionary orderings seem to consider it
 487  * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
 488  * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
 489  * would like to treat numbers intelligently so that "file1" "file10" "file5"
 490  * is sorted as "file1" "file5" "file10".
 491  *
 492  * Note that this function depends on the [current locale][setlocale].
 493  *
 494  * Returns: a newly allocated string. This string should
 495  *   be freed with g_free() when you are done with it.
 496  *
 497  * Since: 2.8
 498  */
 499 gchar *
 500 g_utf8_collate_key_for_filename (const gchar *str,
 501                                  gssize       len)
 502 {
 503 #ifndef HAVE_CARBON
 504   GString *result;
 505   GString *append;
 506   const gchar *p;
 507   const gchar *prev;
 508   const gchar *end;
 509   gchar *collate_key;
 510   gint digits;
 511   gint leading_zeros;
 512
 513   /*
 514    * How it works:
 515    *
 516    * Split the filename into collatable substrings which do
 517    * not contain [.0-9] and special-cased substrings. The collatable
 518    * substrings are run through the normal g_utf8_collate_key() and the
 519    * resulting keys are concatenated with keys generated from the
 520    * special-cased substrings.
 521    *
 522    * Special cases: Dots are handled by replacing them with '\1' which
 523    * implies that short dot-delimited substrings are before long ones,
 524    * e.g.
 525    *
 526    *   a\1a   (a.a)
 527    *   a-\1a  (a-.a)
 528    *   aa\1a  (aa.a)
 529    *
 530    * Numbers are handled by prepending to each number d-1 superdigits
 531    * where d = number of digits in the number and SUPERDIGIT is a
 532    * character with an integer value higher than any digit (for instance
 533    * ':'). This ensures that single-digit numbers are sorted before
 534    * double-digit numbers which in turn are sorted separately from
 535    * triple-digit numbers, etc. To avoid strange side-effects when
 536    * sorting strings that already contain SUPERDIGITs, a '\2'
 537    * is also prepended, like this
 538    *
 539    *   file\21      (file1)
 540    *   file\25      (file5)
 541    *   file\2:10    (file10)
 542    *   file\2:26    (file26)
 543    *   file\2::100  (file100)
 544    *   file:foo     (file:foo)
 545    *
 546    * This has the side-effect of sorting numbers before everything else (except
 547    * dots), but this is probably OK.
 548    *
 549    * Leading digits are ignored when doing the above. To discriminate
 550    * numbers which differ only in the number of leading digits, we append
 551    * the number of leading digits as a byte at the very end of the collation
 552    * key.
 553    *
 554    * To try avoid conflict with any collation key sequence generated by libc we
 555    * start each switch to a special cased part with a sentinel that hopefully
 556    * will sort before anything libc will generate.
 557    */
 558
 559   if (len < 0)
 560     len = strlen (str);
 561
 562   result = g_string_sized_new (len * 2);
 563   append = g_string_sized_new (0);
 564
 565   end = str + len;
 566
 567   /* No need to use utf8 functions, since we're only looking for ascii chars */
 568   for (prev = p = str; p < end; p++)
 569     {
 570       switch (*p)
 571         {
 572         case '.':
 573           if (prev != p)
 574             {
 575               collate_key = g_utf8_collate_key (prev, p - prev);
 576               g_string_append (result, collate_key);
 577               g_free (collate_key);
 578             }
 579
 580           g_string_append (result, COLLATION_SENTINEL "\1");
 581
 582           /* skip the dot */
 583           prev = p + 1;
 584           break;
 585
 586         case '0':
 587         case '1':
 588         case '2':
 589         case '3':
 590         case '4':
 591         case '5':
 592         case '6':
 593         case '7':
 594         case '8':
 595         case '9':
 596           if (prev != p)
 597             {
 598               collate_key = g_utf8_collate_key (prev, p - prev);
 599               g_string_append (result, collate_key);
 600               g_free (collate_key);
 601             }
 602
 603           g_string_append (result, COLLATION_SENTINEL "\2");
 604
 605           prev = p;
 606
 607           /* write d-1 colons */
 608           if (*p == '0')
 609             {
 610               leading_zeros = 1;
 611               digits = 0;
 612             }
 613           else
 614             {
 615               leading_zeros = 0;
 616               digits = 1;
 617             }
 618
 619           while (++p < end)
 620             {
 621               if (*p == '0' && !digits)
 622                 ++leading_zeros;
 623               else if (g_ascii_isdigit(*p))
 624                 ++digits;
 625               else
 626                 {
 627                   /* count an all-zero sequence as
 628                    * one digit plus leading zeros
 629                    */
 630                   if (!digits)
 631                     {
 632                       ++digits;
 633                       --leading_zeros;
 634                     }
 635                   break;
 636                 }
 637             }
 638
 639           while (digits > 1)
 640             {
 641               g_string_append_c (result, ':');
 642               --digits;
 643             }
 644
 645           if (leading_zeros > 0)
 646             {
 647               g_string_append_c (append, (char)leading_zeros);
 648               prev += leading_zeros;
 649             }
 650
 651           /* write the number itself */
 652           g_string_append_len (result, prev, p - prev);
 653
 654           prev = p;
 655           --p;    /* go one step back to avoid disturbing outer loop */
 656           break;
 657
 658         default:
 659           /* other characters just accumulate */
 660           break;
 661         }
 662     }
 663
 664   if (prev != p)
 665     {
 666       collate_key = g_utf8_collate_key (prev, p - prev);
 667       g_string_append (result, collate_key);
 668       g_free (collate_key);
 669     }
 670
 671   g_string_append (result, append->str);
 672   g_string_free (append, TRUE);
 673
 674   return g_string_free (result, FALSE);
 675 #else /* HAVE_CARBON */
 676   return carbon_collate_key_for_filename (str, len);
 677 #endif
 678 }