Re: [ft] Failure in loading U+033F in DejaVu fonts

[suzuki toshiya]

Dear Werner,

The naming convention for the types, variables and functions
need further improvement (sorry for my poor English), and some
compiler warnings should be fixed, but anyway I've drafted
a proof of concept. I confirmed it does not complain DejaVu
but detects the recursive reference in the sample files in
bug #46372.

--

please think about the glyph composed like this.

a-+-b-c-d-e
  +-f-g

in following, I note the node as a:0, the first "a" is
the glyph id, the second "0" is the recursion count.

now, the component is "pushed" to the list.

after parsing the first chain, composites would be like:
[ e:4, d:3, c:2, b:1, a:0 ]

when we push the first node in the 2nd chain, f:1,
the list is rotated until the node whose recursion count
is less than "1" (of f:1). For this rotation, I introduced
FT_List_Down().

the rotated result is
[ a:0, e:4, d:3, c:2, b:1 ]

now, we scan until the root glyph (-:0) from the beginning.
if we find any "f" component, it could be recursive.
if there is no, we push f:1 to the head.

[ f:1, a:0, e:4, d:3, c:2, b:1 ]

by such rotate-then-push process, we can use single chain
to scan single chain from a given node to root.

--

to store the data like "a:0", I introduced a structure
typed as TT_GlyphDecompose (including gid & recurse_count).
therefore, for the memory manager, the cost becomes twice.
original implementation used FT_ListNode->data to store GID.
The memory manager just allocated & freed the node, but,
in my preliminary implementation, the memory manager works
twice - FT_ListNode and TT_GlyphDecompose storage.
Should I consider overwriting (and extend if required)
storategy, to minimize the memory management?

Regards,
mpsuzuki

Werner LEMBERG wrote:
>> It seems that the changeset 758d55e522eb426dad2f15adc1d945f7896d7b29
>> (between 2.6.1 and 2.6.2) is the point that FT2 starts the complain
>> against DejaVu. The changset was introduced to detected looped
>> reference. [...]
> 
> Thanks for your analysis.  It seems that the test to protect against
> recursion is a bit too simple.
> 
>> I guess the composite glyphs referring same component twice or more
>> can cause this warning. I will try to fix it...
> 
> Great! 
> 
> 
>     Werner
> 

diff --git a/include/freetype/ftlist.h b/include/freetype/ftlist.h
index 12b48c7..3e691a7 100644
--- a/include/freetype/ftlist.h
+++ b/include/freetype/ftlist.h
@@ -169,6 +169,23 @@ FT_BEGIN_HEADER
 
   /*************************************************************************/
   /*                                                                       */
+  /* <Function>                                                            */
+  /*    FT_List_Down                                                       */
+  /*                                                                       */
+  /* <Description>                                                         */
+  /*    Move a node to the tail/end of a list.                             */
+  /*                                                                       */
+  /* <InOut>                                                               */
+  /*    list :: A pointer to the parent list.                              */
+  /*    node :: The node to move.                                          */
+  /*                                                                       */
+  FT_EXPORT( void )
+  FT_List_Down( FT_List      list,
+                FT_ListNode  node );
+
+
+  /*************************************************************************/
+  /*                                                                       */
   /* <FuncType>                                                            */
   /*    FT_List_Iterator                                                   */
   /*                                                                       */
diff --git a/src/autofit/afloader.c b/src/autofit/afloader.c
index f37530d..a2036d1 100644
--- a/src/autofit/afloader.c
+++ b/src/autofit/afloader.c
@@ -23,6 +23,7 @@
 #include "afmodule.h"
 #include "afpic.h"
 
+#include FT_INTERNAL_CALC_H
 
   /* Initialize glyph loader. */
 
diff --git a/src/base/ftutil.c b/src/base/ftutil.c
index f5b72db..4947eac 100644
--- a/src/base/ftutil.c
+++ b/src/base/ftutil.c
@@ -375,6 +375,39 @@
 
   /* documentation is in ftlist.h */
 
+  FT_EXPORT_DEF( void )
+  FT_List_Down( FT_List      list,
+                FT_ListNode  node )
+  {
+    FT_ListNode  before, after;
+
+
+    if ( !list || !node )
+      return;
+
+    before = node->prev;
+    after  = node->next;
+
+    /* check whether we are already on end of the list */
+    if ( !after )
+      return;
+
+    after->prev = before;
+
+    if ( before )
+      before->next = after;
+    else
+      list->head = after;
+
+    node->prev       = list->tail;
+    node->next       = NULL;
+    list->tail->next = node;
+    list->tail       = node;
+  }
+
+
+  /* documentation is in ftlist.h */
+
   FT_EXPORT_DEF( FT_Error )
   FT_List_Iterate( FT_List           list,
                    FT_List_Iterator  iterator,
diff --git a/src/truetype/ttgload.c b/src/truetype/ttgload.c
index 9a8b458..276d922 100644
--- a/src/truetype/ttgload.c
+++ b/src/truetype/ttgload.c
@@ -1367,6 +1367,88 @@
 
 #endif /* !TT_CONFIG_OPTION_SUBPIXEL_HINTING */
 
+  /*************************************************************************/
+  /* storage to track the decomposition process, to detect a looped        */
+  /* reference in the composite glyph                                      */
+  typedef struct TT_GlyphDecomp_
+  {
+    FT_UInt  gid;
+    FT_UInt  recurse_count;
+  } TT_GlyphDecomp;
+
+  static TT_GlyphDecomp*
+  tt_new_glyphdecomp( FT_Memory  memory,
+                      FT_UInt    gid,
+                      FT_UInt    recurse_count )
+  {
+    FT_Error error;
+    TT_GlyphDecomp *gd = NULL;
+    if ( !FT_ALLOC(gd, sizeof(TT_GlyphDecomp)) )
+    {
+      FT_TRACE5(( " tt_new_glyphdecomp: allocate for {%d, %d} @ %p\n", gid, 
recurse_count, gd ));
+      gd->gid = gid;
+      gd->recurse_count = recurse_count;
+    }
+
+    return gd;
+  }
+
+  static void
+  tt_destroy_glyphdecomp( FT_Memory        memory,
+                          TT_GlyphDecomp*  gd,
+                          void*            user )
+  {
+    FT_TRACE5(( " tt_destroy_glyphdecomp: free {%d, %d} @ %p\n", gd->gid, 
gd->recurse_count, gd ));
+    FT_FREE( gd );
+  }
+
+  typedef enum TT_GlyphDecompLookupStat_
+  {
+    TT_BEFORE_ROOT_GLYPH,
+    TT_PASSED_ROOT_GLYPH
+  } TT_GlyphDecompLookupStat;
+
+  typedef struct TT_GlyphDecompLookup_
+  {
+    TT_GlyphDecomp  gd;
+    TT_GlyphDecompLookupStat stat;
+  } TT_GlyphDecompLookup;
+
+
+  static FT_Error
+  tt_lookup_earlier_glyphdecomp( FT_ListNode      node,
+                                 TT_GlyphDecompLookup*  lookup )
+  {
+    TT_GlyphDecomp*  gd_node = (TT_GlyphDecomp*)(node->data);
+    TT_GlyphDecomp*  gd_lookup = (TT_GlyphDecomp*)(&(lookup->gd));
+    if ( lookup->stat == TT_PASSED_ROOT_GLYPH || gd_node->recurse_count == 0 ) 
{ 
+      FT_TRACE5(( " tt_lookup_earlier_glyphdecomp: reached the root glyph 
(%d)\n", gd_node->gid ));
+      lookup->stat = TT_PASSED_ROOT_GLYPH;
+      return FT_Err_Ok;
+    }
+    if ( gd_node->gid != gd_lookup->gid )
+    {
+      FT_TRACE5(( " tt_lookup_earlier_glyphdecomp: different gid (%d != 
%d)\n", gd_node->gid, gd_lookup->gid ));
+      return FT_Err_Ok;
+    }
+    if ( gd_node->recurse_count < gd_lookup->recurse_count )
+    {
+      FT_TRACE5(( " tt_lookup_earlier_glyphdecomp: found earlier occurence (%d 
< %d)\n", gd_node->recurse_count, gd_lookup->recurse_count ));
+      return FT_Err_Invalid_Composite;
+    }
+    FT_TRACE5(( " tt_lookup_earlier_glyphdecomp: found later occurence (%d >= 
%d)\n", gd_node->recurse_count, gd_lookup->recurse_count ));
+    return FT_Err_Ok;
+  }
+
+  static FT_Error
+  tt_dump_glyphdecomp( FT_ListNode  node,
+                       void*        user )
+  {
+    TT_GlyphDecomp*  gd_node = (TT_GlyphDecomp*)(node->data);
+    FT_TRACE5(( " tt_dump_glyphdecomp: {%d, %d}\n", gd_node->gid, 
gd_node->recurse_count ));
+    return FT_Err_Ok;
+  }
+
 
   /*************************************************************************/
   /*                                                                       */
@@ -1639,10 +1721,27 @@
       FT_UInt   start_point;
       FT_UInt   start_contour;
       FT_ULong  ins_pos;  /* position of composite instructions, if any */
-
+      TT_GlyphDecompLookup lookup = { { glyph_index, recurse_count }, 
TT_BEFORE_ROOT_GLYPH };
 
       /* check whether we already have a composite glyph with this index */
-      if ( FT_List_Find( &loader->composites, (void*)glyph_index ) )
+      FT_TRACE2(( "TT_Load_Composite_Glyph: lookup gid-%d in 
loader->composites (%p)\n", glyph_index, &(loader->composites) ));
+
+      {
+        while (loader->composites.head) {
+          TT_GlyphDecomp* top_gd = 
(TT_GlyphDecomp*)(loader->composites.head->data);
+          if (top_gd->recurse_count == recurse_count - 1)
+            break;
+           
+          FT_TRACE2(( "TT_Load_Composite_Glyph: move {gid=%d:recurse=%d} to 
the end of loader->composites (%p)\n",
+                                                      top_gd->gid, 
top_gd->recurse_count, &(loader->composites) ));
+          FT_List_Down( &loader->composites, loader->composites.head );
+          
+        }
+        FT_List_Iterate( &loader->composites, 
(FT_List_Iterator)tt_dump_glyphdecomp, NULL );
+      }
+
+
+      if ( FT_List_Iterate( &loader->composites, 
(FT_List_Iterator)tt_lookup_earlier_glyphdecomp, &lookup ) )
       {
         FT_TRACE1(( "TT_Load_Composite_Glyph:"
                     " infinite recursion detected\n" ));
@@ -1656,9 +1755,12 @@
 
         if ( FT_NEW( node ) )
           goto Exit;
-        node->data = (void*)glyph_index;
-        FT_List_Add( &loader->composites, node );
+        node->data = (void*)tt_new_glyphdecomp( memory, glyph_index, 
recurse_count );
+
+        FT_TRACE2(( "TT_Load_Composite_Glyph: append gid-%d to 
loader->composites (%p)\n", glyph_index, &(loader->composites) ));
+        FT_List_Insert( &loader->composites, node );
       }
+      FT_List_Iterate( &loader->composites, 
(FT_List_Iterator)tt_dump_glyphdecomp, NULL );
 
       start_point   = (FT_UInt)gloader->base.outline.n_points;
       start_contour = (FT_UInt)gloader->base.outline.n_contours;
@@ -2419,6 +2521,7 @@
     loader->glyph  = (FT_GlyphSlot)glyph;
     loader->stream = stream;
 
+    FT_TRACE2(( "tt_loader_init(): initialize loader->composites (%p)\n", 
&(loader->composites) ));
     loader->composites.head = NULL;
     loader->composites.tail = NULL;
 
@@ -2429,8 +2532,9 @@
   static void
   tt_loader_done( TT_Loader  loader )
   {
+    FT_TRACE2(( "tt_loader_done(): finalize loader->composites (%p)\n", 
&(loader->composites) ));
     FT_List_Finalize( &loader->composites,
-                      NULL,
+                      (FT_List_Destructor)tt_destroy_glyphdecomp,
                       loader->face->root.memory,
                       NULL );
   }