[ft] wip: looped reference detection (Re: Failure in loading U+033F in DejaVu fonts)

[suzuki toshiya]

Dear Werner,

The original detection was sufficient for the case:

the composition tree is something like
a-+-b-c-b
  +-d
  +-e

the composites list would be "a-b-c-b-d-e", and it can
detect the loop at the 2nd occurrence of b.

In DejaVu case, the structure is

a-+-b
  +-b

and the composites list would be "a-b-b", and
it can confuse the detector at the 2nd occurrence of b.

Just I've scratched an idea as attached one;
* record both of gid & recursion count into loader->composites.
* if same gid is found at the earlier recursion count, it is recognized as loop.

the composites list for the former case would be
"a:1 - b:2 - c:3 - b:4 - d:2 - e:2", we can detect the loop
by the existence of "b:2" and "b:4".
the composites list for the latter case would be
"a:1 - b:2 - b:2", we can expect that it is repeated but not looped.

It works for DejaVu, but soon I found this check was insufficient.
the case like
a-+-b-c-d
  +-e-f-b
can confuse my scratch again (b:2 and b:4 would be recognized
as looped).

Now I think we should ignore the "b-c-d" chain when we
are tracking "e-f-b" chain.

I think repeating alloc & free during the process of glyph
composition is not good idea (although I've not checked its overhead).
Maybe I will propose new function FT_List_Down() which moves
the specified node to the end of the list.

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/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/truetype/ttgload.c b/src/truetype/ttgload.c
index 9a8b458..96208b6 100644
--- a/src/truetype/ttgload.c
+++ b/src/truetype/ttgload.c
@@ -1367,6 +1367,62 @@
 
 #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;
+    FT_ALLOC( gd, sizeof(TT_GlyphDecomp) );
+
+    if (!error)
+    {
+      FT_TRACE5(( " tt_new_glyphdecomp: allocate for {%d, %d} @ 0x%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} @ 0x%p\n", gd->gid, 
gd->recurse_count, gd ));
+    FT_FREE( gd );
+  }
+
+  static FT_Error
+  tt_lookup_earlier_glyphdecomp( FT_ListNode      node,
+                                 TT_GlyphDecomp*  gd_lookup )
+  {
+    TT_GlyphDecomp*  gd_node = (TT_GlyphDecomp*)(node->data);
+    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;
+  }
+
 
   /*************************************************************************/
   /*                                                                       */
@@ -1639,10 +1695,12 @@
       FT_UInt   start_point;
       FT_UInt   start_contour;
       FT_ULong  ins_pos;  /* position of composite instructions, if any */
+      TT_GlyphDecomp  gd_cur = { glyph_index, recurse_count };
 
 
       /* 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) ));
+      if ( FT_List_Iterate( &loader->composites, 
(FT_List_Iterator)tt_lookup_earlier_glyphdecomp, &gd_cur ) )
       {
         FT_TRACE1(( "TT_Load_Composite_Glyph:"
                     " infinite recursion detected\n" ));
@@ -1656,7 +1714,8 @@
 
         if ( FT_NEW( node ) )
           goto Exit;
-        node->data = (void*)glyph_index;
+        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_Add( &loader->composites, node );
       }
 
@@ -2419,6 +2478,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 +2489,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 );
   }