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