fribidi.c

GTK+-2.0源码之pango-1.15.6.tar.gz

/* FriBidi - Library of BiDi algorithm
 * Copyright (C) 1999,2000 Dov Grobgeld, and
 * Copyright (C) 2001,2002 Behdad Esfahbod.
 * 
 * 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, in a file named COPYING; if not, write to the
 * Free Software Foundation, Inc., 59 Temple Place, Suite 330,
 * Boston, MA 02111-1307, USA
 * 
 * For licensing issues, contact <[e-mail]> and
 * <[e-mail]>.
 */

#include <config.h>
#include <stdlib.h>
#include <string.h>

#include "fribidi.h"

/* Redefine FRIBIDI_CHUNK_SIZE in config.h to override this. */
#ifndef FRIBIDI_CHUNK_SIZE
#ifdef MEM_OPTIMIZED
#define FRIBIDI_CHUNK_SIZE 16
#else
#define FRIBIDI_CHUNK_SIZE 128
#endif
#endif

#define DBG(s)
#define DBG2(s, t)

/*======================================================================
 * Typedef for the run-length list.
 *----------------------------------------------------------------------*/
typedef struct _TypeLink TypeLink;

struct _TypeLink
{
  TypeLink *prev;
  TypeLink *next;

  FriBidiCharType type;
  FriBidiStrIndex pos, len;
  FriBidiLevel level;
};

#define FRIBIDI_LEVEL_START   -1
#define FRIBIDI_LEVEL_END     -1
#define FRIBIDI_LEVEL_REMOVED -2

typedef struct
{
  FriBidiCharType override;	/* only L, R and N are valid */
  FriBidiLevel level;
}
LevelInfo;

static TypeLink *
new_type_link (void)
{
  TypeLink *link;

  link = g_slice_new0 (TypeLink);

  return link;
}

static void
free_type_link (TypeLink *link)
{
  g_slice_free (TypeLink, link);
}

#define FRIBIDI_ADD_TYPE_LINK(p,q) \
	do {	\
		(p)->len = (q)->pos - (p)->pos;	\
		(p)->next = (q);	\
		(q)->prev = (p);	\
		(p) = (q);	\
	} while (0)

static TypeLink *
run_length_encode_types_utf8 (const char *s,
			      int bytelen,
			      FriBidiStrIndex *len,
			      FriBidiCharType *pored_types,
			      FriBidiCharType *panded_strongs)
{
  TypeLink *list, *last, *link;
  FriBidiCharType char_type;
  FriBidiCharType ored_types = 0;
  FriBidiCharType anded_strongs = FRIBIDI_TYPE_RLE;
  FriBidiStrIndex i;
  const char *p;

  /* Add the starting link */
  list = new_type_link ();
  list->type = FRIBIDI_TYPE_SOT;
  list->level = FRIBIDI_LEVEL_START;
  last = list;

  /* Sweep over the string s */
  i = 0;
  for (p = s; p < s + bytelen; p = g_utf8_next_char(p)) {
    char_type = fribidi_get_type (g_utf8_get_char (p));
    ored_types |= char_type;
    if (FRIBIDI_IS_STRONG (char_type))
      anded_strongs &= char_type;
    if (char_type != last->type)
      {
	link = new_type_link ();
	link->type = char_type;
	link->pos = i;
	FRIBIDI_ADD_TYPE_LINK (last, link);
      }
    i++;
  }

  /* Add the ending link */
  link = new_type_link ();
  link->type = FRIBIDI_TYPE_EOT;
  link->level = FRIBIDI_LEVEL_END;
  link->pos = i;
  FRIBIDI_ADD_TYPE_LINK (last, link);

  if (len)
    *len = i;

  if (pored_types)
    *pored_types = ored_types;
  if (panded_strongs)
    *panded_strongs = anded_strongs; 

  return list;
}

/* explicits_list is a list like type_rl_list, that holds the explicit
   codes that are removed from rl_list, to reinsert them later by calling
   the override_list.
*/
static void
init_list (TypeLink **start,
	   TypeLink **end)
{
  TypeLink *list;
  TypeLink *link;

  /* Add the starting link */
  list = new_type_link ();
  list->type = FRIBIDI_TYPE_SOT;
  list->level = FRIBIDI_LEVEL_START;
  list->len = 0;
  list->pos = 0;

  /* Add the ending link */
  link = new_type_link ();
  link->type = FRIBIDI_TYPE_EOT;
  link->level = FRIBIDI_LEVEL_END;
  link->len = 0;
  link->pos = 0;
  list->next = link;
  link->prev = list;

  *start = list;
  *end = link;
}

/* move an element before another element in a list, the list must have a
   previous element, used to update explicits_list.
   assuming that p have both prev and next or none of them, also update
   the list that p is currently in, if any.
*/
static void
move_element_before (TypeLink *p,
		     TypeLink *list)
{
  if (p->prev)
    {
      p->prev->next = p->next;
      p->next->prev = p->prev;
    }
  p->prev = list->prev;
  list->prev->next = p;
  p->next = list;
  list->prev = p;
}

/* override the rl_list 'base', with the elements in the list 'over', to
   reinsert the previously-removed explicit codes (at X9) from
   'explicits_list' back into 'type_rl_list'. This is used at the end of I2
   to restore the explicit marks, and also to reset the character types of
   characters at L1.

   it is assumed that the 'pos' of the first element in 'base' list is not
   more than the 'pos' of the first element of the 'over' list, and the
   'pos' of the last element of the 'base' list is not less than the 'pos'
   of the last element of the 'over' list. these two conditions are always
   satisfied for the two usages mentioned above.

   TBD: use some explanatory names instead of p, q, ...
*/
static void
override_list (TypeLink *base,
	       TypeLink *over)
{
  TypeLink *p = base, *q, *r, *s, *t;
  FriBidiStrIndex pos = 0, pos2;

  if (!over)
    return;
  q = over;
  while (q)
    {
      if (!q->len || q->pos < pos)
	{
	  t = q;
	  q = q->next;
	  free_type_link (t);
	  continue;
	}
      pos = q->pos;
      while (p->next && p->next->pos <= pos)
	p = p->next;
      /* now p is the element that q must be inserted 'in'. */
      pos2 = pos + q->len;
      r = p;
      while (r->next && r->next->pos < pos2)
	r = r->next;
      /* now r is the last element that q affects. */
      if (p == r)
	{
	  /* split p into at most 3 interval, and insert q in the place of
	     the second interval, set r to be the third part. */
	  /* third part needed? */
	  if (p->next && p->next->pos == pos2)
	    r = r->next;
	  else
	    {
	      r = new_type_link ();
	      *r = *p;
	      if (r->next)
		{
		  r->next->prev = r;
		  r->len = r->next->pos - pos2;
		}
	      else
		r->len -= pos - p->pos;
	      r->pos = pos2;
	    }
	  /* first part needed? */
	  if (p->prev && p->pos == pos)
	    {
	      t = p;
	      p = p->prev;
	      free_type_link (t);
	    }
	  else
	    p->len = pos - p->pos;
	}
      else
	{
	  /* cut the end of p. */
	  p->len = pos - p->pos;
	  /* if all of p is cut, remove it. */
	  if (!p->len && p->prev)
	    p = p->prev;

	  /* cut the begining of r. */
	  r->pos = pos2;
	  if (r->next)
	    r->len = r->next->pos - pos2;
	  /* if all of r is cut, remove it. */
	  if (!r->len && r->next)
	    r = r->next;

	  /* remove the elements between p and r. */
	  for (s = p->next; s != r;)
	    {
	      t = s;
	      s = s->next;
	      free_type_link (t);
	    }
	}
      /* before updating the next and prev links to point to the inserted q,
         we must remember the next element of q in the 'over' list.
       */
      t = q;
      q = q->next;
      p->next = t;
      t->prev = p;
      t->next = r;
      r->prev = t;
    }
}

/* Some convenience macros */
#define RL_TYPE(list) ((list)->type)
#define RL_LEN(list) ((list)->len)
#define RL_POS(list) ((list)->pos)
#define RL_LEVEL(list) ((list)->level)

static TypeLink *
merge_with_prev (TypeLink *second)
{
  TypeLink *first = second->prev;
  first->next = second->next;
  first->next->prev = first;
  RL_LEN (first) += RL_LEN (second);
  free_type_link (second);
  return first;
}

static void
compact_list (TypeLink *list)
{
  if (list->next)
    for (list = list->next; list; list = list->next)
      if (RL_TYPE (list->prev) == RL_TYPE (list)
	  && RL_LEVEL (list->prev) == RL_LEVEL (list))
	list = merge_with_prev (list);
}

static void
compact_neutrals (TypeLink *list)
{
  if (list->next)
    {
      for (list = list->next; list; list = list->next)
	{
	  if (RL_LEVEL (list->prev) == RL_LEVEL (list)
	      &&
	      ((RL_TYPE
		(list->prev) == RL_TYPE (list)
		|| (FRIBIDI_IS_NEUTRAL (RL_TYPE (list->prev))
		    && FRIBIDI_IS_NEUTRAL (RL_TYPE (list))))))
	    list = merge_with_prev (list);
	}
    }
}

/*======================================================================
 *  Frees up the rl_list, must be called after each call to
 *  fribidi_analyse_string(), after the list is not needed anymore.
 *----------------------------------------------------------------------*/
static void
free_rl_list (TypeLink *type_rl_list)
{
  DBG ("Entering free_rl_list()\n");

  if (!type_rl_list)
    {
      DBG ("Leaving free_rl_list()\n");
      return;
    }

  g_slice_free_chain (TypeLink, type_rl_list, next);

  DBG ("Leaving free_rl_list()\n");
  return;
}

/*=========================================================================
 * define macros for push and pop the status in to / out of the stack
 *-------------------------------------------------------------------------*/

/* There's some little points in pushing and poping into the status stack:
   1. when the embedding level is not valid (more than UNI_MAX_BIDI_LEVEL=61),
   you must reject it, and not to push into the stack, but when you see a
   PDF, you must find the matching code, and if it was pushed in the stack,
   pop it, it means you must pop if and only if you have pushed the
   matching code, the over_pushed var counts the number of rejected codes yet.
   2. there's a more confusing point too, when the embedding level is exactly
   UNI_MAX_BIDI_LEVEL-1=60, an LRO or LRE must be rejected because the new
   level would be UNI_MAX_BIDI_LEVEL+1=62, that is invalid, but an RLO or RLE
   must be accepted because the new level is UNI_MAX_BIDI_LEVEL=61, that is
   valid, so the rejected codes may be not continuous in the logical order,
   in fact there is at most two continuous intervals of codes, with a RLO or
   RLE between them.  To support this case, the first_interval var counts the
   number of rejected codes in the first interval, when it is 0, means that
   there is only one interval yet.
*/

/* a. If this new level would be valid, then this embedding code is valid.
   Remember (push) the current embedding level and override status.
   Reset current level to this new level, and reset the override status to
   new_override.
   b. If the new level would not be valid, then this code is invalid. Don't
   change the current level or override status.
*/
#define PUSH_STATUS \
    do { \
      if (new_level <= UNI_MAX_BIDI_LEVEL) \
        { \
          if (level == UNI_MAX_BIDI_LEVEL - 1) \
            first_interval = over_pushed; \
          status_stack[stack_size].level = level; \
          status_stack[stack_size].override = override; \
          stack_size++; \
          level = new_level; \
          override = new_override; \
        } else \
	  over_pushed++; \
    } while (0)

/* If there was a valid matching code, restore (pop) the last remembered
   (pushed) embedding level and directional override.
*/
#define POP_STATUS \
    do { \
      if (over_pushed || stack_size) \
      { \
        if (over_pushed > first_interval) \
          over_pushed--; \
        else \
          { \
            if (over_pushed == first_interval) \
              first_interval = 0; \
            stack_size--; \
            level = status_stack[stack_size].level; \
            override = status_stack[stack_size].override; \
          } \
      } \
    } while (0)

/*==========================================================================
 * There was no support for sor and eor in the absence of Explicit Embedding
 * Levels, so define macros, to support them, with as less change as needed.
 *--------------------------------------------------------------------------*/

/* Return the type of previous char or the sor, if already at the start of
   a run level. */
#define PREV_TYPE_OR_SOR(pp) \
    ( \
     RL_LEVEL(pp->prev) == RL_LEVEL(pp) ? \
      RL_TYPE(pp->prev) : \
      FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->prev), RL_LEVEL(pp))) \
    )

/* Return the type of next char or the eor, if already at the end of
   a run level. */
#define NEXT_TYPE_OR_EOR(pp) \
    ( \
     !pp->next ? \
      FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(pp)) : \
      (RL_LEVEL(pp->next) == RL_LEVEL(pp) ? \
        RL_TYPE(pp->next) : \
        FRIBIDI_LEVEL_TO_DIR(MAX(RL_LEVEL(pp->next), RL_LEVEL(pp))) \
      ) \
    )


/* Return the embedding direction of a link. */
#define FRIBIDI_EMBEDDING_DIRECTION(list) \
    FRIBIDI_LEVEL_TO_DIR(RL_LEVEL(list))


/*======================================================================
 *  This function should follow the Unicode specification closely!
 *----------------------------------------------------------------------*/
static fribidi_boolean
fribidi_analyse_string_utf8 (	/* input */
			 const char *str,
			 int bytelen,
			 FriBidiCharType *pbase_dir,
			 /* output */
			 FriBidiStrIndex *len,
			 TypeLink **ptype_rl_list,
			 FriBidiLevel *pmax_level)
{