Fix the GObject Visual Studio Projects
[platform/upstream/glib.git] / 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 = 0;
221   const gsize start = 2 * sizeof (void *) / sizeof (UCCollationValue);
222   gsize i;
223
224   /* The first codes should be skipped: the same string on the same
225    * system can get different values at runtime in those positions,
226    * and they do not sort correctly.  The exact size of the prefix
227    * depends on whether we are building 64 or 32 bit.
228    */
229   if (key_len <= start)
230     return g_strdup ("");
231
232   for (i = start; i < key_len; i++)
233     result_len += utf8_encode (NULL, g_htonl (key[i] + 1));
234
235   result = g_malloc (result_len + 1);
236   result_len = 0;
237   for (i = start; i < key_len; i++)
238     result_len += utf8_encode (result + result_len, g_htonl (key[i] + 1));
239
240   result[result_len] = '\0';
241
242   return result;
243 }
244
245 static gchar *
246 carbon_collate_key_with_collator (const gchar *str,
247                                   gssize       len,
248                                   CollatorRef  collator)
249 {
250   UniChar *str_utf16 = NULL;
251   glong len_utf16;
252   OSStatus ret;
253   UCCollationValue staticbuf[512];
254   UCCollationValue *freeme = NULL;
255   UCCollationValue *buf;
256   ItemCount buf_len;
257   ItemCount key_len;
258   ItemCount try_len;
259   gchar *result = NULL;
260
261   str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);
262   try_len = len_utf16 * 5 + 2;
263
264   if (try_len <= sizeof staticbuf)
265     {
266       buf = staticbuf;
267       buf_len = sizeof staticbuf;
268     }
269   else
270     {
271       freeme = g_new (UCCollationValue, try_len);
272       buf = freeme;
273       buf_len = try_len;
274     }
275
276   ret = UCGetCollationKey (collator, str_utf16, len_utf16,
277                            buf_len, &key_len, buf);
278
279   if (ret == kCollateBufferTooSmall)
280     {
281       freeme = g_renew (UCCollationValue, freeme, try_len * 2);
282       buf = freeme;
283       buf_len = try_len * 2;
284       ret = UCGetCollationKey (collator, str_utf16, len_utf16,
285                                buf_len, &key_len, buf);
286     }
287
288   if (ret == 0)
289     result = collate_key_to_string (buf, key_len);
290   else
291     result = g_strdup ("");
292
293   g_free (freeme);
294   g_free (str_utf16);
295   return result;
296 }
297
298 static gchar *
299 carbon_collate_key (const gchar *str,
300                     gssize       len)
301 {
302   static CollatorRef collator;
303
304   if (G_UNLIKELY (!collator))
305     {
306       UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);
307
308       if (!collator)
309         {
310           static gboolean been_here;
311           if (!been_here)
312             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
313           been_here = TRUE;
314           return g_strdup ("");
315         }
316     }
317
318   return carbon_collate_key_with_collator (str, len, collator);
319 }
320
321 static gchar *
322 carbon_collate_key_for_filename (const gchar *str,
323                                  gssize       len)
324 {
325   static CollatorRef collator;
326
327   if (G_UNLIKELY (!collator))
328     {
329       /* http://developer.apple.com/qa/qa2004/qa1159.html */
330       UCCreateCollator (NULL, 0,
331                         kUCCollateComposeInsensitiveMask
332                          | kUCCollateWidthInsensitiveMask
333                          | kUCCollateCaseInsensitiveMask
334                          | kUCCollateDigitsOverrideMask
335                          | kUCCollateDigitsAsNumberMask
336                          | kUCCollatePunctuationSignificantMask, 
337                         &collator);
338
339       if (!collator)
340         {
341           static gboolean been_here;
342           if (!been_here)
343             g_warning ("%s: UCCreateCollator failed", G_STRLOC);
344           been_here = TRUE;
345           return g_strdup ("");
346         }
347     }
348
349   return carbon_collate_key_with_collator (str, len, collator);
350 }
351
352 #endif /* HAVE_CARBON */
353
354 /**
355  * g_utf8_collate_key:
356  * @str: a UTF-8 encoded string.
357  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
358  *
359  * Converts a string into a collation key that can be compared
360  * with other collation keys produced by the same function using 
361  * strcmp(). 
362  *
363  * The results of comparing the collation keys of two strings 
364  * with strcmp() will always be the same as comparing the two 
365  * original keys with g_utf8_collate().
366  * 
367  * Note that this function depends on the 
368  * <link linkend="setlocale">current locale</link>.
369  * 
370  * Return value: a newly allocated string. This string should
371  *   be freed with g_free() when you are done with it.
372  **/
373 gchar *
374 g_utf8_collate_key (const gchar *str,
375                     gssize       len)
376 {
377   gchar *result;
378
379 #ifdef HAVE_CARBON
380
381   g_return_val_if_fail (str != NULL, NULL);
382   result = carbon_collate_key (str, len);
383
384 #elif defined(__STDC_ISO_10646__)
385
386   gsize xfrm_len;
387   gunichar *str_norm;
388   wchar_t *result_wc;
389   gsize i;
390   gsize result_len = 0;
391
392   g_return_val_if_fail (str != NULL, NULL);
393
394   str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);
395
396   xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);
397   result_wc = g_new (wchar_t, xfrm_len + 1);
398   wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);
399
400   for (i=0; i < xfrm_len; i++)
401     result_len += utf8_encode (NULL, result_wc[i]);
402
403   result = g_malloc (result_len + 1);
404   result_len = 0;
405   for (i=0; i < xfrm_len; i++)
406     result_len += utf8_encode (result + result_len, result_wc[i]);
407
408   result[result_len] = '\0';
409
410   g_free (result_wc);
411   g_free (str_norm);
412
413   return result;
414 #else /* !__STDC_ISO_10646__ */
415
416   gsize xfrm_len;
417   const gchar *charset;
418   gchar *str_norm;
419
420   g_return_val_if_fail (str != NULL, NULL);
421
422   str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);
423
424   result = NULL;
425
426   if (g_get_charset (&charset))
427     {
428       xfrm_len = strxfrm (NULL, str_norm, 0);
429       if (xfrm_len >= 0 && xfrm_len < G_MAXINT - 2)
430         {
431           result = g_malloc (xfrm_len + 1);
432           strxfrm (result, str_norm, xfrm_len + 1);
433         }
434     }
435   else
436     {
437       gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);
438
439       if (str_locale)
440         {
441           xfrm_len = strxfrm (NULL, str_locale, 0);
442           if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)
443             {
444               g_free (str_locale);
445               str_locale = NULL;
446             }
447         }
448       if (str_locale)
449         {
450           result = g_malloc (xfrm_len + 2);
451           result[0] = 'A';
452           strxfrm (result + 1, str_locale, xfrm_len + 1);
453           
454           g_free (str_locale);
455         }
456     }
457     
458   if (!result) 
459     {
460       xfrm_len = strlen (str_norm);
461       result = g_malloc (xfrm_len + 2);
462       result[0] = 'B';
463       memcpy (result + 1, str_norm, xfrm_len);
464       result[xfrm_len+1] = '\0';
465     }
466
467   g_free (str_norm);
468 #endif /* __STDC_ISO_10646__ */
469
470   return result;
471 }
472
473 /* This is a collation key that is very very likely to sort before any
474    collation key that libc strxfrm generates. We use this before any
475    special case (dot or number) to make sure that its sorted before
476    anything else.
477  */
478 #define COLLATION_SENTINEL "\1\1\1"
479
480 /**
481  * g_utf8_collate_key_for_filename:
482  * @str: a UTF-8 encoded string.
483  * @len: length of @str, in bytes, or -1 if @str is nul-terminated.
484  *
485  * Converts a string into a collation key that can be compared
486  * with other collation keys produced by the same function using strcmp(). 
487  * 
488  * In order to sort filenames correctly, this function treats the dot '.' 
489  * as a special case. Most dictionary orderings seem to consider it
490  * insignificant, thus producing the ordering "event.c" "eventgenerator.c"
491  * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we
492  * would like to treat numbers intelligently so that "file1" "file10" "file5"
493  * is sorted as "file1" "file5" "file10".
494  * 
495  * Note that this function depends on the 
496  * <link linkend="setlocale">current locale</link>.
497  *
498  * Return value: a newly allocated string. This string should
499  *   be freed with g_free() when you are done with it.
500  *
501  * Since: 2.8
502  */
503 gchar*
504 g_utf8_collate_key_for_filename (const gchar *str,
505                                  gssize       len)
506 {
507 #ifndef HAVE_CARBON
508   GString *result;
509   GString *append;
510   const gchar *p;
511   const gchar *prev;
512   const gchar *end;
513   gchar *collate_key;
514   gint digits;
515   gint leading_zeros;
516
517   /*
518    * How it works:
519    *
520    * Split the filename into collatable substrings which do
521    * not contain [.0-9] and special-cased substrings. The collatable 
522    * substrings are run through the normal g_utf8_collate_key() and the 
523    * resulting keys are concatenated with keys generated from the 
524    * special-cased substrings.
525    *
526    * Special cases: Dots are handled by replacing them with '\1' which 
527    * implies that short dot-delimited substrings are before long ones, 
528    * e.g.
529    * 
530    *   a\1a   (a.a)
531    *   a-\1a  (a-.a)
532    *   aa\1a  (aa.a)
533    * 
534    * Numbers are handled by prepending to each number d-1 superdigits 
535    * where d = number of digits in the number and SUPERDIGIT is a 
536    * character with an integer value higher than any digit (for instance 
537    * ':'). This ensures that single-digit numbers are sorted before 
538    * double-digit numbers which in turn are sorted separately from 
539    * triple-digit numbers, etc. To avoid strange side-effects when 
540    * sorting strings that already contain SUPERDIGITs, a '\2'
541    * is also prepended, like this
542    *
543    *   file\21      (file1)
544    *   file\25      (file5)
545    *   file\2:10    (file10)
546    *   file\2:26    (file26)
547    *   file\2::100  (file100)
548    *   file:foo     (file:foo)
549    * 
550    * This has the side-effect of sorting numbers before everything else (except
551    * dots), but this is probably OK.
552    *
553    * Leading digits are ignored when doing the above. To discriminate
554    * numbers which differ only in the number of leading digits, we append
555    * the number of leading digits as a byte at the very end of the collation
556    * key.
557    *
558    * To try avoid conflict with any collation key sequence generated by libc we
559    * start each switch to a special cased part with a sentinel that hopefully
560    * will sort before anything libc will generate.
561    */
562
563   if (len < 0)
564     len = strlen (str);
565
566   result = g_string_sized_new (len * 2);
567   append = g_string_sized_new (0);
568
569   end = str + len;
570
571   /* No need to use utf8 functions, since we're only looking for ascii chars */
572   for (prev = p = str; p < end; p++)
573     {
574       switch (*p)
575         {
576         case '.':
577           if (prev != p) 
578             {
579               collate_key = g_utf8_collate_key (prev, p - prev);
580               g_string_append (result, collate_key);
581               g_free (collate_key);
582             }
583           
584           g_string_append (result, COLLATION_SENTINEL "\1");
585           
586           /* skip the dot */
587           prev = p + 1;
588           break;
589           
590         case '0':
591         case '1':
592         case '2':
593         case '3':
594         case '4':
595         case '5':
596         case '6':
597         case '7':
598         case '8':
599         case '9':
600           if (prev != p) 
601             {
602               collate_key = g_utf8_collate_key (prev, p - prev);
603               g_string_append (result, collate_key);
604               g_free (collate_key);
605             }
606           
607           g_string_append (result, COLLATION_SENTINEL "\2");
608           
609           prev = p;
610           
611           /* write d-1 colons */
612           if (*p == '0')
613             {
614               leading_zeros = 1;
615               digits = 0;
616             }
617           else
618             {
619               leading_zeros = 0;
620               digits = 1;
621             }
622           
623           while (++p < end)
624             {
625               if (*p == '0' && !digits)
626                 ++leading_zeros;
627               else if (g_ascii_isdigit(*p))
628                 ++digits;
629               else
630                 {
631                   /* count an all-zero sequence as
632                    * one digit plus leading zeros
633                    */
634                   if (!digits)
635                     {
636                       ++digits;
637                       --leading_zeros;
638                     }        
639                   break;
640                 }
641             }
642
643           while (digits > 1)
644             {
645               g_string_append_c (result, ':');
646               --digits;
647             }
648
649           if (leading_zeros > 0)
650             {
651               g_string_append_c (append, (char)leading_zeros);
652               prev += leading_zeros;
653             }
654           
655           /* write the number itself */
656           g_string_append_len (result, prev, p - prev);
657           
658           prev = p;
659           --p;    /* go one step back to avoid disturbing outer loop */
660           break;
661           
662         default:
663           /* other characters just accumulate */
664           break;
665         }
666     }
667   
668   if (prev != p) 
669     {
670       collate_key = g_utf8_collate_key (prev, p - prev);
671       g_string_append (result, collate_key);
672       g_free (collate_key);
673     }
674   
675   g_string_append (result, append->str);
676   g_string_free (append, TRUE);
677
678   return g_string_free (result, FALSE);
679 #else /* HAVE_CARBON */
680   return carbon_collate_key_for_filename (str, len);
681 #endif
682 }