/* gunicollate.c - Collation

 *

 *  Copyright 2001,2005 Red Hat, Inc.

 *

 * This library is free software; you can redistribute it and/or

 * modify it under the terms of the GNU Lesser General Public

 * License as published by the Free Software Foundation; either

 * version 2.1 of the License, or (at your option) any later version.

 *

 * This library 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.  See the GNU

 * Lesser General Public License for more details.

 *

 * You should have received a copy of the GNU Lesser General Public License

 * along with this library; if not, see <http://www.gnu.org/licenses/>.

 */

#include "config.h"

#include <locale.h>

#include <string.h>

#ifdef HAVE_WCHAR_H

#include <wchar.h>

#endif

#ifdef HAVE_CARBON

#include <CoreServices/CoreServices.h>

#endif

#include "gmem.h"

#include "gunicode.h"

#include "gunicodeprivate.h"

#include "gstring.h"

#include "gstrfuncs.h"

#include "gtestutils.h"

#include "gcharset.h"

#include "gconvert.h"

#if SIZEOF_WCHAR_T == 4 && defined(__STDC_ISO_10646__)

#define GUNICHAR_EQUALS_WCHAR_T 1

#endif

#ifdef _MSC_VER

/* Workaround for bug in MSVCR80.DLL */

static gsize

msc_strxfrm_wrapper (char       *string1,

         const char *string2,

         gsize       count)

{

  if (!string1 || count <= 0)

    {

      char tmp;

      return strxfrm (&tmp, string2, 1);

    }

  return strxfrm (string1, string2, count);

}

#define strxfrm msc_strxfrm_wrapper

#endif

/**

 * g_utf8_collate:

 * @str1: a UTF-8 encoded string

 * @str2: a UTF-8 encoded string

 * 

 * Compares two strings for ordering using the linguistically

 * correct rules for the [current locale][setlocale].

 * When sorting a large number of strings, it will be significantly 

 * faster to obtain collation keys with g_utf8_collate_key() and 

 * compare the keys with strcmp() when sorting instead of sorting 

 * the original strings.

 * 

 * Returns: < 0 if @str1 compares before @str2, 

 *   0 if they compare equal, > 0 if @str1 compares after @str2.

 **/

gint

g_utf8_collate (const gchar *str1,

    const gchar *str2)

{

  gint result;

#ifdef HAVE_CARBON

  UniChar *str1_utf16;

  UniChar *str2_utf16;

  glong len1;

  glong len2;

  SInt32 retval = 0;

  g_return_val_if_fail (str1 != NULL, 0);

  g_return_val_if_fail (str2 != NULL, 0);

  str1_utf16 = g_utf8_to_utf16 (str1, -1, NULL, &len1, NULL);

  str2_utf16 = g_utf8_to_utf16 (str2, -1, NULL, &len2, NULL);

  UCCompareTextDefault (kUCCollateStandardOptions,

                        str1_utf16, len1, str2_utf16, len2,

                        NULL, &retval);

  result = retval;

  g_free (str2_utf16);

  g_free (str1_utf16);

#elif defined(HAVE_WCHAR_H) && defined(GUNICHAR_EQUALS_WCHAR_T)

  gunichar *str1_norm;

  gunichar *str2_norm;

  g_return_val_if_fail (str1 != NULL, 0);

  g_return_val_if_fail (str2 != NULL, 0);

  str1_norm = _g_utf8_normalize_wc (str1, -1, G_NORMALIZE_ALL_COMPOSE);

  str2_norm = _g_utf8_normalize_wc (str2, -1, G_NORMALIZE_ALL_COMPOSE);

  result = wcscoll ((wchar_t *)str1_norm, (wchar_t *)str2_norm);

  g_free (str1_norm);

  g_free (str2_norm);

#else

  const gchar *charset;

  gchar *str1_norm;

  gchar *str2_norm;

  g_return_val_if_fail (str1 != NULL, 0);

  g_return_val_if_fail (str2 != NULL, 0);

  str1_norm = g_utf8_normalize (str1, -1, G_NORMALIZE_ALL_COMPOSE);

  str2_norm = g_utf8_normalize (str2, -1, G_NORMALIZE_ALL_COMPOSE);

  if (g_get_charset (&charset))

    {

      result = strcoll (str1_norm, str2_norm);

    }

  else

    {

      gchar *str1_locale = g_convert (str1_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

      gchar *str2_locale = g_convert (str2_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

      if (str1_locale && str2_locale)

  result =  strcoll (str1_locale, str2_locale);

      else if (str1_locale)

  result = -1;

      else if (str2_locale)

  result = 1;

      else

  result = strcmp (str1_norm, str2_norm);

      g_free (str1_locale);

      g_free (str2_locale);

    }

  g_free (str1_norm);

  g_free (str2_norm);

#endif

  return result;

}

#if defined(HAVE_WCHAR_H) && defined(GUNICHAR_EQUALS_WCHAR_T)

/* We need UTF-8 encoding of numbers to encode the weights if

 * we are using wcsxfrm. However, we aren't encoding Unicode

 * characters, so we can't simply use g_unichar_to_utf8.

 *

 * The following routine is taken (with modification) from GNU

 * libc's strxfrm routine:

 *

 * Copyright (C) 1995-1999,2000,2001 Free Software Foundation, Inc.

 * Written by Ulrich Drepper <drepper@cygnus.com>, 1995.

 */

static inline int

utf8_encode (char *buf, wchar_t val)

{

  int retval;

  if (val < 0x80)

    {

      if (buf)

  *buf++ = (char) val;

      retval = 1;

    }

  else

    {

      int step;

      for (step = 2; step < 6; ++step)

        if ((val & (~(guint32)0 << (5 * step + 1))) == 0)

          break;

      retval = step;

      if (buf)

  {

    *buf = (unsigned char) (~0xff >> step);

    --step;

    do

      {

        buf[step] = 0x80 | (val & 0x3f);

        val >>= 6;

      }

    while (--step > 0);

    *buf |= val;

  }

    }

  return retval;

}

#endif

#ifdef HAVE_CARBON

static gchar *

collate_key_to_string (UCCollationValue *key,

                       gsize             key_len)

{

  gchar *result;

  gsize result_len;

  long *lkey = (long *) key;

  /* UCCollationValue format:

   *

   * UCCollateOptions (32/64 bits)

   * SizeInBytes      (32/64 bits)

   * Value            (8 bits arrey)

   *

   * UCCollateOptions: ordering option mask of the collator

   * used to create the key. Size changes on 32-bit / 64-bit

   * hosts. On 64-bits also the extra half-word seems to have

   * some extra (unknown) meaning.

   * SizeInBytes: size of the whole structure, in bytes

   * (including UCCollateOptions and SizeInBytes fields). Size

   * changes on 32-bit & 64-bit hosts.

   * Value: array of bytes containing the comparison weights.

   * Seems to have several sub-strings separated by \001 and \002

   * chars. Also, experience shows this is directly strcmp-able.

   */

  result_len = lkey[1];

  result = g_malloc (result_len + 1);

  memcpy (result, &lkey[2], result_len);

  result[result_len] = '\0';

  return result;

}

static gchar *

carbon_collate_key_with_collator (const gchar *str,

                                  gssize       len,

                                  CollatorRef  collator)

{

  UniChar *str_utf16 = NULL;

  glong len_utf16;

  OSStatus ret;

  UCCollationValue staticbuf[512];

  UCCollationValue *freeme = NULL;

  UCCollationValue *buf;

  ItemCount buf_len;

  ItemCount key_len;

  ItemCount try_len;

  gchar *result = NULL;

  str_utf16 = g_utf8_to_utf16 (str, len, NULL, &len_utf16, NULL);

  try_len = len_utf16 * 5 + 2;

  if (try_len <= sizeof staticbuf)

    {

      buf = staticbuf;

      buf_len = sizeof staticbuf;

    }

  else

    {

      freeme = g_new (UCCollationValue, try_len);

      buf = freeme;

      buf_len = try_len;

    }

  ret = UCGetCollationKey (collator, str_utf16, len_utf16,

                           buf_len, &key_len, buf);

  if (ret == kCollateBufferTooSmall)

    {

      freeme = g_renew (UCCollationValue, freeme, try_len * 2);

      buf = freeme;

      buf_len = try_len * 2;

      ret = UCGetCollationKey (collator, str_utf16, len_utf16,

                               buf_len, &key_len, buf);

    }

  if (ret == 0)

    result = collate_key_to_string (buf, key_len);

  else

    result = g_strdup ("");

  g_free (freeme);

  g_free (str_utf16);

  return result;

}

static gchar *

carbon_collate_key (const gchar *str,

                    gssize       len)

{

  static CollatorRef collator;

  if (G_UNLIKELY (!collator))

    {

      UCCreateCollator (NULL, 0, kUCCollateStandardOptions, &collator);

      if (!collator)

        {

          static gboolean been_here;

          if (!been_here)

            g_warning ("%s: UCCreateCollator failed", G_STRLOC);

          been_here = TRUE;

          return g_strdup ("");

        }

    }

  return carbon_collate_key_with_collator (str, len, collator);

}

static gchar *

carbon_collate_key_for_filename (const gchar *str,

                                 gssize       len)

{

  static CollatorRef collator;

  if (G_UNLIKELY (!collator))

    {

      /* http://developer.apple.com/qa/qa2004/qa1159.html */

      UCCreateCollator (NULL, 0,

                        kUCCollateComposeInsensitiveMask

                         | kUCCollateWidthInsensitiveMask

                         | kUCCollateCaseInsensitiveMask

                         | kUCCollateDigitsOverrideMask

                         | kUCCollateDigitsAsNumberMask

                         | kUCCollatePunctuationSignificantMask, 

                        &collator);

      if (!collator)

        {

          static gboolean been_here;

          if (!been_here)

            g_warning ("%s: UCCreateCollator failed", G_STRLOC);

          been_here = TRUE;

          return g_strdup ("");

        }

    }

  return carbon_collate_key_with_collator (str, len, collator);

}

#endif /* HAVE_CARBON */

/**

 * g_utf8_collate_key:

 * @str: a UTF-8 encoded string.

 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.

 *

 * Converts a string into a collation key that can be compared

 * with other collation keys produced by the same function using 

 * strcmp(). 

 *

 * The results of comparing the collation keys of two strings 

 * with strcmp() will always be the same as comparing the two 

 * original keys with g_utf8_collate().

 * 

 * Note that this function depends on the [current locale][setlocale].

 * 

 * Returns: a newly allocated string. This string should

 *   be freed with g_free() when you are done with it.

 **/

gchar *

g_utf8_collate_key (const gchar *str,

        gssize       len)

{

  gchar *result;

#ifdef HAVE_CARBON

  g_return_val_if_fail (str != NULL, NULL);

  result = carbon_collate_key (str, len);

#elif defined(HAVE_WCHAR_H) && defined(GUNICHAR_EQUALS_WCHAR_T)

  gsize xfrm_len;

  gunichar *str_norm;

  wchar_t *result_wc;

  gsize i;

  gsize result_len = 0;

  g_return_val_if_fail (str != NULL, NULL);

  str_norm = _g_utf8_normalize_wc (str, len, G_NORMALIZE_ALL_COMPOSE);

  xfrm_len = wcsxfrm (NULL, (wchar_t *)str_norm, 0);

  result_wc = g_new (wchar_t, xfrm_len + 1);

  wcsxfrm (result_wc, (wchar_t *)str_norm, xfrm_len + 1);

  for (i = 0; i < xfrm_len; i++)

    result_len += utf8_encode (NULL, result_wc[i]);

  result = g_malloc (result_len + 1);

  result_len = 0;

  for (i = 0; i < xfrm_len; i++)

    result_len += utf8_encode (result + result_len, result_wc[i]);

  result[result_len] = '\0';

  g_free (result_wc);

  g_free (str_norm);

  return result;

#else

  gsize xfrm_len;

  const gchar *charset;

  gchar *str_norm;

  g_return_val_if_fail (str != NULL, NULL);

  str_norm = g_utf8_normalize (str, len, G_NORMALIZE_ALL_COMPOSE);

  result = NULL;

  if (g_get_charset (&charset))

    {

      xfrm_len = strxfrm (NULL, str_norm, 0);

      if (xfrm_len < G_MAXINT - 2)

        {

          result = g_malloc (xfrm_len + 1);

          strxfrm (result, str_norm, xfrm_len + 1);

        }

    }

  else

    {

      gchar *str_locale = g_convert (str_norm, -1, charset, "UTF-8", NULL, NULL, NULL);

      if (str_locale)

  {

    xfrm_len = strxfrm (NULL, str_locale, 0);

    if (xfrm_len < 0 || xfrm_len >= G_MAXINT - 2)

      {

        g_free (str_locale);

        str_locale = NULL;

      }

  }

      if (str_locale)

  {

    result = g_malloc (xfrm_len + 2);

    result[0] = 'A';

    strxfrm (result + 1, str_locale, xfrm_len + 1);

    g_free (str_locale);

  }

    }

  if (!result) 

    {

      xfrm_len = strlen (str_norm);

      result = g_malloc (xfrm_len + 2);

      result[0] = 'B';

      memcpy (result + 1, str_norm, xfrm_len);

      result[xfrm_len+1] = '\0';

    }

  g_free (str_norm);

#endif

  return result;

}

/* This is a collation key that is very very likely to sort before any

 * collation key that libc strxfrm generates. We use this before any

 * special case (dot or number) to make sure that its sorted before

 * anything else.

 */

#define COLLATION_SENTINEL "\1\1\1"

/**

 * g_utf8_collate_key_for_filename:

 * @str: a UTF-8 encoded string.

 * @len: length of @str, in bytes, or -1 if @str is nul-terminated.

 *

 * Converts a string into a collation key that can be compared

 * with other collation keys produced by the same function using strcmp(). 

 * 

 * In order to sort filenames correctly, this function treats the dot '.' 

 * as a special case. Most dictionary orderings seem to consider it

 * insignificant, thus producing the ordering "event.c" "eventgenerator.c"

 * "event.h" instead of "event.c" "event.h" "eventgenerator.c". Also, we

 * would like to treat numbers intelligently so that "file1" "file10" "file5"

 * is sorted as "file1" "file5" "file10".

 * 

 * Note that this function depends on the [current locale][setlocale].

 *

 * Returns: a newly allocated string. This string should

 *   be freed with g_free() when you are done with it.

 *

 * Since: 2.8

 */

gchar *

g_utf8_collate_key_for_filename (const gchar *str,

         gssize       len)

{

#ifndef HAVE_CARBON

  GString *result;

  GString *append;

  const gchar *p;

  const gchar *prev;

  const gchar *end;

  gchar *collate_key;

  gint digits;

  gint leading_zeros;

  /*

   * How it works:

   *

   * Split the filename into collatable substrings which do

   * not contain [.0-9] and special-cased substrings. The collatable 

   * substrings are run through the normal g_utf8_collate_key() and the 

   * resulting keys are concatenated with keys generated from the 

   * special-cased substrings.

   *

   * Special cases: Dots are handled by replacing them with '\1' which 

   * implies that short dot-delimited substrings are before long ones, 

   * e.g.

   * 

   *   a\1a   (a.a)

   *   a-\1a  (a-.a)

   *   aa\1a  (aa.a)

   * 

   * Numbers are handled by prepending to each number d-1 superdigits 

   * where d = number of digits in the number and SUPERDIGIT is a 

   * character with an integer value higher than any digit (for instance 

   * ':'). This ensures that single-digit numbers are sorted before 

   * double-digit numbers which in turn are sorted separately from 

   * triple-digit numbers, etc. To avoid strange side-effects when 

   * sorting strings that already contain SUPERDIGITs, a '\2'

   * is also prepended, like this

   *

   *   file\21      (file1)

   *   file\25      (file5)

   *   file\2:10    (file10)

   *   file\2:26    (file26)

   *   file\2::100  (file100)

   *   file:foo     (file:foo)

   * 

   * This has the side-effect of sorting numbers before everything else (except

   * dots), but this is probably OK.

   *

   * Leading digits are ignored when doing the above. To discriminate

   * numbers which differ only in the number of leading digits, we append

   * the number of leading digits as a byte at the very end of the collation

   * key.

   *

   * To try avoid conflict with any collation key sequence generated by libc we

   * start each switch to a special cased part with a sentinel that hopefully

   * will sort before anything libc will generate.

   */

  if (len < 0)

    len = strlen (str);

  result = g_string_sized_new (len * 2);

  append = g_string_sized_new (0);

  end = str + len;

  /* No need to use utf8 functions, since we're only looking for ascii chars */

  for (prev = p = str; p < end; p++)

    {

      switch (*p)

  {

  case '.':

    if (prev != p) 

      {

        collate_key = g_utf8_collate_key (prev, p - prev);

        g_string_append (result, collate_key);

        g_free (collate_key);

      }

    g_string_append (result, COLLATION_SENTINEL "\1");

    /* skip the dot */

    prev = p + 1;

    break;

  case '0':

  case '1':

  case '2':

  case '3':

  case '4':

  case '5':

  case '6':

  case '7':

  case '8':

  case '9':

    if (prev != p) 

      {

        collate_key = g_utf8_collate_key (prev, p - prev);

        g_string_append (result, collate_key);

        g_free (collate_key);

      }

    g_string_append (result, COLLATION_SENTINEL "\2");

    prev = p;

    /* write d-1 colons */

    if (*p == '0')

      {

        leading_zeros = 1;

        digits = 0;

      }

    else

      {

        leading_zeros = 0;

        digits = 1;

      }

    while (++p < end)

      {

        if (*p == '0' && !digits)

    ++leading_zeros;

        else if (g_ascii_isdigit(*p))

    ++digits;

        else

                {

      /* count an all-zero sequence as

                   * one digit plus leading zeros

                   */

              if (!digits)

                    {

                      ++digits;

                      --leading_zeros;

                    }        

      break;

                }

      }

    while (digits > 1)

      {

        g_string_append_c (result, ':');

        --digits;

      }

    if (leading_zeros > 0)

      {

        g_string_append_c (append, (char)leading_zeros);

        prev += leading_zeros;

      }

    /* write the number itself */

    g_string_append_len (result, prev, p - prev);

    prev = p;

    --p;    /* go one step back to avoid disturbing outer loop */

    break;

  default:

    /* other characters just accumulate */

    break;

  }

    }

  if (prev != p) 

    {

      collate_key = g_utf8_collate_key (prev, p - prev);

      g_string_append (result, collate_key);

      g_free (collate_key);

    }

  g_string_append (result, append->str);

  g_string_free (append, TRUE);

  return g_string_free (result, FALSE);

#else /* HAVE_CARBON */

  return carbon_collate_key_for_filename (str, len);

#endif

}