text: /* Pango
   * pangocoretext-shape.c
   *
   * Copyright (C) 2005 Imendio AB
   * Copyright (C) 2010  Kristian Rietveld  <kris@gtk.org>
   * Copyright (C) 2012  Kristian Rietveld  <kris@lanedo.com>
   *
   * This library is free software; you can redistribute it and/or
   * modify it under the terms of the GNU Library General Public
   * License as published by the Free Software Foundation; either
   * version 2 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
   * Library General Public License for more details.
   *
   * You should have received a copy of the GNU Library General Public
   * License along with this library; if not, write to the
   * Free Software Foundation, Inc., 59 Temple Place - Suite 330,
   * Boston, MA 02111-1307, USA.
   */
  
  #include "config.h"
  #include <glib.h>
  #include <string.h>
  #include <Carbon/Carbon.h>
  #include "pango-utils.h"
  #include "pangocoretext-private.h"
  #include "pango-impl-utils.h"
  
  #if defined(MAC_OS_X_VERSION_MAX_ALLOWED) && MAC_OS_X_VERSION_MAX_ALLOWED < 1060
  CF_INLINE Boolean CFStringIsSurrogateHighCharacter(UniChar character) {
      return ((character >= 0xD800UL) && (character <= 0xDBFFUL) ? true : false);
  }
  
  CF_INLINE Boolean CFStringIsSurrogateLowCharacter(UniChar character) {
      return ((character >= 0xDC00UL) && (character <= 0xDFFFUL) ? true : false);
  }
  
  CF_INLINE UTF32Char CFStringGetLongCharacterForSurrogatePair(UniChar surrogateHigh, UniChar surrogateLow) {
      return ((surrogateHigh - 0xD800UL) << 10) + (surrogateLow - 0xDC00UL) + 0x0010000UL;
  }
  #endif
  
  static void
  set_glyph (PangoFont        *font,
  	   PangoGlyphString *glyphs,
  	   int               i,
  	   int               offset,
  	   PangoGlyph        glyph)
  {
    PangoRectangle logical_rect;
  
    glyphs->glyphs[i].glyph = glyph;
  
    glyphs->glyphs[i].geometry.x_offset = 0;
    glyphs->glyphs[i].geometry.y_offset = 0;
  
    glyphs->log_clusters[i] = offset;
    pango_font_get_glyph_extents (font, glyphs->glyphs[i].glyph, NULL, &logical_rect);
    glyphs->glyphs[i].geometry.width = logical_rect.width;
  }
  
  
  /* The "RunIterator" helps us to iterate over the array of runs that is obtained from
   * the CoreText type setter. Even though Pango considers the string that is passed to
   * the shape function a single run, CoreText might consider it to consist out of
   * multiple runs. Because of this, we have an interface around the CoreText array of
   * runs that works like iterating a single array, which makes our job in the shape
   * function easier.
   */
  
  struct RunIterator
  {
    CTLineRef line;
    CFStringRef cstr;
    CFArrayRef runs;
    CFIndex glyph_count;
  
    CFIndex total_ct_i;
    CFIndex ct_i;
  
    CFIndex *chr_idx_lut;
  
    int current_run_number;
    CTRunRef current_run;
    CFIndex *current_indices;
    const CGGlyph *current_cgglyphs;
    CGGlyph *current_cgglyphs_buffer;
    CTRunStatus current_run_status;
  };
  
  static void
  run_iterator_free_current_run (struct RunIterator *iter)
  {
    iter->current_run_number = -1;
    iter->current_run = NULL;
    iter->current_cgglyphs = NULL;
    if (iter->current_cgglyphs_buffer)
      free (iter->current_cgglyphs_buffer);
    iter->current_cgglyphs_buffer = NULL;
    if (iter->current_indices)
      free (iter->current_indices);
    iter->current_indices = NULL;
  }
  
  static void
  run_iterator_set_current_run (struct RunIterator *iter,
                                const int           run_number)
  {
    CFIndex ct_glyph_count;
  
    run_iterator_free_current_run (iter);
  
    iter->current_run_number = run_number;
    iter->current_run = CFArrayGetValueAtIndex (iter->runs, run_number);
    ct_glyph_count = CTRunGetGlyphCount (iter->current_run);
  
    iter->current_run_status = CTRunGetStatus (iter->current_run);
    iter->current_cgglyphs = CTRunGetGlyphsPtr (iter->current_run);
    if (!iter->current_cgglyphs)
      {
        iter->current_cgglyphs_buffer = (CGGlyph *)malloc (sizeof (CGGlyph) * ct_glyph_count);
        CTRunGetGlyphs (iter->current_run, CFRangeMake (0, ct_glyph_count),
                        iter->current_cgglyphs_buffer);
        iter->current_cgglyphs = iter->current_cgglyphs_buffer;
      }
  
    iter->current_indices = malloc (sizeof (CFIndex) * ct_glyph_count);
    CTRunGetStringIndices (iter->current_run, CFRangeMake (0, ct_glyph_count),
                           iter->current_indices);
  
    iter->ct_i = 0;
  }
  
  static CFIndex
  run_iterator_get_glyph_count (struct RunIterator *iter)
  {
    CFIndex accumulator = 0;
    CFIndex i;
  
    for (i = 0; i < CFArrayGetCount (iter->runs); i++)
      accumulator += CTRunGetGlyphCount (CFArrayGetValueAtIndex (iter->runs, i));
  
    return accumulator;
  }
  
  /* This function generates a lookup table to match string indices of glyphs to
   * actual unicode character indices. This also takes unicode characters into
   * account that are encoded using 2 UTF16 code points in CFStrings. We use the
   * unicode character index to match up with the unicode characters in the UTF8
   * string provided by Pango.
   */
  static CFIndex *
  run_iterator_get_chr_idx_lut (CFStringRef cstr)
  {
    CFIndex cstr_length = CFStringGetLength (cstr);
    CFIndex *chr_idx_lut = malloc (sizeof (CFIndex) * cstr_length);
    CFIndex i;
    CFIndex current_value = 0;
  
    for (i = 0; i < cstr_length; i++)
      {
        chr_idx_lut[i] = current_value;
  
        if (CFStringIsSurrogateHighCharacter (CFStringGetCharacterAtIndex (cstr, i)) &&
            i + 1 < cstr_length &&
            CFStringIsSurrogateLowCharacter (CFStringGetCharacterAtIndex (cstr, i + 1)))
          continue;
  
        current_value++;
      }
  
    return chr_idx_lut;
  }
  
  /* These functions are commented out to silence the compiler, but
   * kept around because they might be of use when fixing the more
   * intricate issues noted in the comment in the function
   * pangocoretext_shape() below.
   */
  #if 0
  static gboolean
  run_iterator_is_rtl (struct RunIterator *iter)
  {
    /* Assume run status is equal for all runs? */
    CTRunStatus run_status = CTRunGetStatus (CFArrayGetValueAtIndex (iter->runs, 0));
  
    return run_status & kCTRunStatusRightToLeft;
  }
  
  static gboolean
  run_iterator_run_is_non_monotonic (struct RunIterator *iter)
  {
    CTRunStatus run_status = CTRunGetStatus (iter->current_run);
  
    return run_status & kCTRunStatusNonMonotonic;
  }
  #endif
  
  static gunichar
  run_iterator_get_character (struct RunIterator *iter)
  {
    UniChar ch = CFStringGetCharacterAtIndex (iter->cstr, iter->current_indices[iter->ct_i]);
  
    if (CFStringIsSurrogateHighCharacter (ch) &&
        iter->current_indices[iter->ct_i] + 1 < CFStringGetLength (iter->cstr))
      {
        UniChar ch2 = CFStringGetCharacterAtIndex (iter->cstr, iter->current_indices[iter->ct_i]+1);
  
        if (CFStringIsSurrogateLowCharacter (ch2))
          return CFStringGetLongCharacterForSurrogatePair (ch, ch2);
      }
  
    return ch;
  }
  
  static CGGlyph
  run_iterator_get_cgglyph (struct RunIterator *iter)
  {
    return iter->current_cgglyphs[iter->ct_i];
  }
  
  static CFIndex
  run_iterator_get_index (struct RunIterator *iter)
  {
    return iter->chr_idx_lut[iter->current_indices[iter->ct_i]];
  }
  
  static gboolean
  run_iterator_create (struct RunIterator *iter,
                       const char         *text,
                       const gint          length,
                       CTFontRef           ctfont)
  {
    char *copy;
    CFDictionaryRef attributes;
    CFAttributedStringRef attstr;
  
    CFTypeRef keys[] = {
        (CFTypeRef) kCTFontAttributeName
    };
  
    CFTypeRef values[] = {
        ctfont
    };
  
    /* Initialize RunIterator structure */
    iter->current_run_number = -1;
    iter->current_run = NULL;
    iter->current_indices = NULL;
    iter->chr_idx_lut = NULL;
    iter->current_cgglyphs = NULL;
    iter->current_cgglyphs_buffer = NULL;
  
    /* Create CTLine */
    attributes = CFDictionaryCreate (kCFAllocatorDefault,
                                     (const void **)keys,
                                     (const void **)values,
                                     1,
                                     &kCFCopyStringDictionaryKeyCallBacks,
                                     &kCFTypeDictionaryValueCallBacks);
  
    copy = g_strndup (text, length + 1);
    copy[length] = 0;
  
    iter->cstr = CFStringCreateWithCString (kCFAllocatorDefault, copy,
                                            kCFStringEncodingUTF8);
    g_free (copy);
  
    if (!iter->cstr)
      /* Creating a CFString can fail if the input string does not
       * adhere to the specified encoding (i.e. it contains invalid UTF8).
       */
      return FALSE;
  
    attstr = CFAttributedStringCreate (kCFAllocatorDefault,
                                       iter->cstr,
                                       attributes);
  
    iter->line = CTLineCreateWithAttributedString (attstr);
    iter->runs = CTLineGetGlyphRuns (iter->line);
  
    CFRelease (attstr);
    CFRelease (attributes);
  
    iter->chr_idx_lut = run_iterator_get_chr_idx_lut (iter->cstr);
  
    iter->total_ct_i = 0;
    iter->glyph_count = run_iterator_get_glyph_count (iter);
  
    /* If CoreText did not render any glyphs for this string (can happen,
     * e.g. a run solely consisting of a BOM), glyph_count will be zero and
     * we immediately set the iterator variable to indicate end of glyph list.
     */
    if (iter->glyph_count > 0)
      run_iterator_set_current_run (iter, 0);
    else
      iter->total_ct_i = -1;
  
    return TRUE;
  }
  
  static void
  run_iterator_free (struct RunIterator *iter)
  {
    run_iterator_free_current_run (iter);
  
    free (iter->chr_idx_lut);
  
    CFRelease (iter->line);
    CFRelease (iter->cstr);
  }
  
  static gboolean
  run_iterator_at_end (struct RunIterator *iter)
  {
    if (iter->total_ct_i == -1)
      return TRUE;
  
    return FALSE;
  }
  
  static void
  run_iterator_advance (struct RunIterator *iter)
  {
    if (iter->total_ct_i >= iter->glyph_count - 1)
      {
        run_iterator_free_current_run (iter);
        iter->ct_i = iter->total_ct_i = -1;
      }
    else
      {
        iter->total_ct_i++;
        iter->ct_i++;
  
        if (iter->total_ct_i < iter->glyph_count &&
            iter->ct_i >= CTRunGetGlyphCount (iter->current_run))
          {
            iter->current_run_number++;
            run_iterator_set_current_run (iter, iter->current_run_number);
          }
      }
  }
  
  
  
  struct GlyphInfo
  {
    CFIndex index;
    CGGlyph cgglyph;
    gunichar wc;
  };
  
  static gint
  glyph_info_compare_func (gconstpointer a, gconstpointer b)
  {
    const struct GlyphInfo *gi_a = a;
    const struct GlyphInfo *gi_b = b;
  
    if (gi_a->index < gi_b->index)
      return -1;
    else if (gi_a->index > gi_b->index)
      return 1;
    /* else */
    return 0;
  }
  
  static void
  glyph_info_free (gpointer data, gpointer user_data)
  {
    g_slice_free (struct GlyphInfo, data);
  }
  
  static GSList *
  create_core_text_glyph_list (const char *text,
                               gint        length,
                               CTFontRef   ctfont)
  {
    GSList *glyph_list = NULL;
    struct RunIterator riter;
  
    if (!run_iterator_create (&riter, text, length, ctfont))
      return NULL;
  
    while (!run_iterator_at_end (&riter))
      {
        struct GlyphInfo *gi;
  
        gi = g_slice_new (struct GlyphInfo);
        gi->index = run_iterator_get_index (&riter);
        gi->cgglyph = run_iterator_get_cgglyph (&riter);
        gi->wc = run_iterator_get_character (&riter);
  
        glyph_list = g_slist_prepend (glyph_list, gi);
  
        run_iterator_advance (&riter);
      }
  
    glyph_list = g_slist_sort (glyph_list, glyph_info_compare_func);
  
    run_iterator_free (&riter);
  
    return glyph_list;
  }
  
  
  void
  _pango_core_text_shape (PangoFont           *font,
  			const char          *text,
  			gint                 length,
  			const PangoAnalysis *analysis,
  			PangoGlyphString    *glyphs,
  			const char          *paragraph_text G_GNUC_UNUSED,
  			unsigned int         paragraph_length G_GNUC_UNUSED)
  {
    const char *p;
    gulong n_chars, gs_i, gs_prev_i;
    PangoCoreTextFont *cfont = PANGO_CORE_TEXT_FONT (font);
    PangoCoverage *coverage;
    GSList *glyph_list;
    GSList *glyph_iter;
  
    /* We first fully iterate over the glyph sequence generated by CoreText and
     * store this into a list, which is sorted after the iteration. We make a pass
     * over the sorted linked list to build up the PangoGlyphString.
     *
     * We have to do this in order to properly handle a bunch of characteristics of the
     * glyph sequence generated by the CoreText typesetter:
     *   # E.g. zero-width spaces do not end up in the CoreText glyph sequence. We have
     *     to manually account for the gap in the character indices.
     *   # Sometimes, CoreText generates two glyph for the same character index. We
     *     currently handle this "properly" as in we do not crash or corrupt memory,
     *     but that's about it.
     *   # Due to mismatches in size, the CoreText glyph sequence can either be longer or
     *     shorter than the PangoGlyphString. Note that the size of the PangoGlyphString
     *     should match the number of characters in "text".
     *
     * If performance becomes a problem, it is certainly possible to use a faster code
     * that only does a single iteration over the string for "simple cases". Simple cases
     * could include these that only consist out of one run (simple Latin text), which
     * don't have gaps in the glyph sequence and which are monotonically
     * increasing/decreasing.
     *
     * FIXME items for future fixing:
     *   # We currently don't bother about LTR, Pango core appears to fix this up for us.
     *     (Even when we cared warnings were generated that strings were in the wrong
     *     order, this should be investigated).
     *   # When CoreText generates two glyphs for one character, only one is stored.
     *     This breaks the example strings for e.g. Georgian and Gothic.
     */
  
    glyph_list = create_core_text_glyph_list (text, length,
                                              pango_core_text_font_get_ctfont (cfont));
    if (!glyph_list)
      return;
  
    /* Set up for translation of the glyph list to a PangoGlyphString. */
    n_chars = pango_utf8_strlen (text, length);
    pango_glyph_string_set_size (glyphs, n_chars);
  
    glyph_iter = glyph_list;
  
    coverage = pango_font_get_coverage (PANGO_FONT (cfont),
                                        analysis->language);
  
    /* gs_i is the index into the Pango glyph string. gi is the iterator into
     * the (CoreText) glyph list, gi->index is the index into the CFString.
     * In matching, we want gs_i and gi->index to match up.
     */
    for (gs_prev_i = -1, gs_i = 0, p = text; gs_i < n_chars;
         gs_prev_i = gs_i, gs_i++, p = g_utf8_next_char (p))
      {
        struct GlyphInfo *gi = glyph_iter != NULL ? glyph_iter->data : NULL;
  
        if (gi == NULL || gi->index > gs_i)
          {
            /* The glyph string is behind, insert an empty glyph to catch
             * up with the CoreText glyph list. This occurs for instance when
             * CoreText inserts a ligature that covers two characters.
             */
            set_glyph (font, glyphs, gs_i, p - text, PANGO_GLYPH_EMPTY);
            continue;
          }
        else if (gi->index < gs_i)
          {
            /* The CoreText glyph list is behind, fast forward the iterator
             * to catch up. This can happen when CoreText emits two glyphs
             * for once character, which is (as noted in the FIXME) above
             * not handled by us yet.
             */
            while (gi && gi->index < gs_i)
              {
                glyph_iter = g_slist_next (glyph_iter);
                if (glyph_iter)
                  gi = glyph_iter->data;
                else
                  gi = NULL;
              }
          }
  
        if (gi != NULL && gi->index == gs_i)
          {
            gunichar mirrored_ch;
            PangoCoverageLevel result;
  
            if (analysis->level % 2)
              if (g_unichar_get_mirror_char (gi->wc, &mirrored_ch))
                gi->wc = mirrored_ch;
  
            if (gi->wc == 0xa0)	/* non-break-space */
              gi->wc = 0x20;
  
            result = pango_coverage_get (coverage, gi->wc);
  
            if (result != PANGO_COVERAGE_NONE)
              {
                set_glyph (font, glyphs, gs_i, p - text, gi->cgglyph);
  
                if (g_unichar_type (gi->wc) == G_UNICODE_NON_SPACING_MARK)
                  {
                    if (gi->index > 0)
                      {
                        PangoRectangle logical_rect, ink_rect;
  
                        glyphs->glyphs[gs_i].geometry.width = MAX (glyphs->glyphs[gs_prev_i].geometry.width,
                                                                   glyphs->glyphs[gs_i].geometry.width);
                        glyphs->glyphs[gs_prev_i].geometry.width = 0;
                        glyphs->log_clusters[gs_i] = glyphs->log_clusters[gs_prev_i];
  
                        /* Some heuristics to try to guess how overstrike glyphs are
                         * done and compensate
                         */
                        pango_font_get_glyph_extents (font, glyphs->glyphs[gs_i].glyph, &ink_rect, &logical_rect);
                        if (logical_rect.width == 0 && ink_rect.x == 0)
                          glyphs->glyphs[gs_i].geometry.x_offset = (glyphs->glyphs[gs_i].geometry.width - ink_rect.width) / 2;
                      }
                  }
              }
            else
              set_glyph (font, glyphs, gs_i, p - text, PANGO_GET_UNKNOWN_GLYPH (gi->wc));
  
            glyph_iter = g_slist_next (glyph_iter);
          }
      }
  
    pango_coverage_unref (coverage);
    g_slist_foreach (glyph_list, glyph_info_free, NULL);
    g_slist_free (glyph_list);
  
    if (analysis->level & 1)
      pango_glyph_string_reverse_range (glyphs, 0, glyphs->num_glyphs);
  }
  