glib/gunicollate.c

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