[freetype2] gsoc-craig-2023-final 49005b96a: [autofit] Add GSUB table handling to reverse character map generation

[Werner Lemberg]

branch: gsoc-craig-2023-final
commit 49005b96a293602afae0e2bd6ff587ca113a80fd
Author: Craig White <gerzytet@gmail.com>
Commit: Craig White <gerzytet@gmail.com>

    [autofit] Add GSUB table handling to reverse character map generation
    * src/autofit/afadjust.c If harfbuzz is enabled, the reverse character
    map generation will now consider GSUB entries when looking for
    glyphs that correspond to a codepoint
---
 src/autofit/afadjust.c | 364 ++++++++++++++++++++++++++++++++++++++++++++++++-
 1 file changed, 362 insertions(+), 2 deletions(-)

diff --git a/src/autofit/afadjust.c b/src/autofit/afadjust.c
index 536956eba..b97aa3244 100644
--- a/src/autofit/afadjust.c
+++ b/src/autofit/afadjust.c
@@ -22,8 +22,6 @@ adjustment_database[] =
     {0x69,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /* i */
     {0x6A,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /* j */
     {0xA1,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /*Inverted Exclamation 
Mark*/
-    {0xBF,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /* j */
-    {0xA1,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /*Inverted Exclamation 
Mark*/
     {0xBF,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /*Inverted Question 
Mark*/
     {0xC0,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /*A with grave*/
     {0xC1,  AF_VERTICAL_ADJUSTMENT_TOP_CONTOUR_UP, 0}, /*A with acute*/
@@ -271,6 +269,318 @@ af_reverse_character_map_expand( AF_ReverseCharacterMap 
map, FT_Long *capacity,
     return FT_Err_Ok;
 }
 
+#ifdef FT_CONFIG_OPTION_USE_HARFBUZZ
+/*
+Recursive algorithm to find all glyphs that a codepoint could turn into from 
the GSUB table.
+
+buffer: a buffer containing only the input codepoint
+feature_tag_pool: the current list of features under consideration
+current_features: the current list of features being applied
+num_features: length of current_features
+result: the set of glyphs that the input codepoint can map to.
+
+The algorithm works by running the hb_ot_shape_glyphs_closure function on 
different lists of features
+to see which features will map to glyph onto something different.  This 
functions returns
+the result of transforming a glyph using a list of features as well as all 
intermediate
+forms if the glyph was transformed multiple times.
+With no features enabled, hb_ot_shape_glyphs_closure will only return the 
glyph given by cmap.
+This character will be the first to be placed into the results set.
+Next, the algorithm will test the same lookup enabline one feature at a time
+and see if any of those features change the result.
+If any new glyph variants are found this way, they are added to the results set
+and the algorithm will recurce, trying that feature in combination will every 
other feature
+to look for further glyph variants.
+
+example:
+suppose we have the following features in the GSUB table:
+f1:
+a -> b
+
+f2:
+b -> c
+
+f3:
+d -> e
+
+The algorithm will take the following steps to find all variants of "a":
+- a is added to the results
+- lookup with feature list {f1}, yielding {a, b}. b is added to the results 
list and the algorithm recurses
+- - lookup with feature list {f1, f2}, yielding {a, b, c}.  c is added to the 
results list and the algorithm recurses
+- - - lookup with feature list {f1, f2, f3} yielding {a, b, c}.  No new glyphs
+- - lookup with feature list {f1, f3}, yielding {a, b}.  No new glyphs
+- lookup with feature list {f2}, yielding {a}. No new glyphs
+- lookup with feature list {f3}, yielding {a}. No new glyphs
+
+*/
+FT_LOCAL_DEF( FT_Error )
+af_all_glyph_variants_helper( hb_font_t *font,
+                              hb_buffer_t *buffer,
+                              hb_set_t *feature_tag_pool,
+                              hb_feature_t *current_features,
+                              FT_UInt32 num_features,
+                              hb_set_t* result )
+{
+    FT_Error error;
+    /*get the list of glyphs that are created by only transforming based on the
+    features in current_features*/
+    hb_set_t *baseline_glyphs = NULL, *new_glyphs = NULL;
+    baseline_glyphs = hb_set_create();
+    if ( !hb_set_allocation_successful( baseline_glyphs ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+
+
+    hb_ot_shape_glyphs_closure ( font,
+                                 buffer,
+                                 current_features,
+                                 num_features,
+                                 baseline_glyphs );
+    if ( !hb_set_allocation_successful( baseline_glyphs ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+    /*Add these baseline glyphs to the results.  The baseline glyphs
+    will contain at minimum the glyph specified by CMAP*/
+    hb_set_union( result, baseline_glyphs );
+    if ( !hb_set_allocation_successful( result ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+    if ( hb_set_get_population( feature_tag_pool ) == 0 )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+    /*setup to try adding different features to current_features
+    to see if any of them have an effect of the glyphs we get from
+    hb_ot_shape_glyphs_closure*/
+    current_features[num_features].start = HB_FEATURE_GLOBAL_START;
+    current_features[num_features].end = HB_FEATURE_GLOBAL_END;
+    current_features[num_features].value = 1; /*set the feature to enabled*/
+    /*quote from docs about value attribute:
+    0 disables the feature, non-zero (usually 1) enables the feature. For 
features implemented as lookup type 3 (like 'salt') the value is a one based 
index into the alternates.
+    this algorithm does not handle these lookup type 3 cases fully*/
+
+    new_glyphs = hb_set_create();
+    if ( !hb_set_allocation_successful( new_glyphs ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+    hb_tag_t feature_tag = HB_SET_VALUE_INVALID;
+    while ( hb_set_next( feature_tag_pool, &feature_tag ) )
+    {
+        hb_set_clear( new_glyphs );
+        current_features[num_features].tag = feature_tag;
+        hb_ot_shape_glyphs_closure ( font,
+                                     buffer,
+                                     current_features,
+                                     num_features + 1,
+                                     new_glyphs );
+        if ( !hb_set_allocation_successful( new_glyphs ) )
+        {
+            error = FT_Err_Out_Of_Memory;
+            goto Exit;
+        }
+
+        hb_set_subtract( new_glyphs, result );
+        /*new_glyphs now contains all glyphs that appeared in the result
+        of hb_ot_shape_glyphs_closure that haven't already been accounted for 
in the result.
+        If this contains any glyphs, we also need to try this feature
+        in combination will other features by recursing
+        */
+        if ( hb_set_get_population( new_glyphs ) != 0 )
+        {
+            /*remove this feature from the feature pool so that
+            the later recursion won't try it*/
+            hb_set_del( feature_tag_pool, feature_tag );
+            error = af_all_glyph_variants_helper( font,
+                                                  buffer,
+                                                  feature_tag_pool,
+                                                  current_features,
+                                                  num_features + 1,
+                                                  result );
+            if ( error )
+            {
+                goto Exit;
+            }
+
+            /*add back the feature we removed*/
+            hb_set_add( feature_tag_pool, feature_tag );
+            if ( !hb_set_allocation_successful( feature_tag_pool ) ) {
+                return FT_Err_Out_Of_Memory;
+            }
+        } /* if( !hb_set_is_subset( glyphs, result ) ) */
+
+    } /*while ( hb_set_next( feature_tag_pool, &feature_tag ) )*/
+Exit:
+    hb_set_destroy( baseline_glyphs );
+    hb_set_destroy( new_glyphs );
+    return FT_Err_Ok;
+}
+
+FT_LOCAL_DEF( FT_Error )
+af_all_glyph_variants( FT_Face face,
+                       hb_font_t *hb_font,
+                       FT_UInt32 codepoint,
+                       hb_set_t* result )
+{
+    FT_Memory memory = face->memory;
+    FT_Error error;
+    hb_face_t *hb_face = hb_font_get_face( hb_font );
+
+    /*The set of all feature tags in the font*/
+    hb_set_t *feature_tags = hb_set_create();
+    hb_set_t *type_3_lookup_indicies = hb_set_create();
+    hb_buffer_t *codepoint_buffer = hb_buffer_create();
+    hb_codepoint_t *type_3_alternate_glyphs_buffer;
+    if ( !hb_set_allocation_successful( feature_tags ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+    if ( !hb_buffer_allocation_successful( codepoint_buffer ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+    if ( !hb_set_allocation_successful ( type_3_lookup_indicies ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+    /*populate feature_tags using the output of 
hb_ot_layout_table_get_feature_tags*/
+    FT_Bool feature_list_done = 0;
+    unsigned int start_offset = 0;
+    while ( !feature_list_done )
+    {
+        unsigned int feature_count = 20;
+        hb_tag_t tags[20];
+        hb_ot_layout_table_get_feature_tags ( hb_face,
+                                              HB_OT_TAG_GSUB,
+                                              start_offset,
+                                              &feature_count,
+                                              tags );
+        start_offset += 20;
+        if ( feature_count < 20 )
+        {
+            feature_list_done = 1;
+        }
+        for ( int i = 0; i < feature_count; i++ )
+        {
+            hb_set_add( feature_tags, tags[i] );
+        }
+        if ( !hb_set_allocation_successful( feature_tags ) )
+        {
+            error = FT_Err_Out_Of_Memory;
+            goto Exit;
+        }
+    }
+
+    /*make a buffer only consisting of the given codepoint*/
+    if ( !hb_buffer_pre_allocate( codepoint_buffer, 1 ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+    hb_buffer_set_direction ( codepoint_buffer,
+                              HB_DIRECTION_LTR );
+    hb_buffer_add( codepoint_buffer, codepoint, 0 );
+
+    /*The array of features that will be used by the recursive part
+    it will have at most as many entries as there are features, so
+    make the length = length of feature_tags*/
+    hb_feature_t *feature_buffer;
+    if (( error = FT_NEW_ARRAY( feature_buffer, hb_set_get_population( 
feature_tags ) ) ))
+    {
+        goto Exit;
+    }
+
+    error = af_all_glyph_variants_helper( hb_font,
+                                          codepoint_buffer,
+                                          feature_tags,
+                                          feature_buffer,
+                                          0,
+                                          result );
+    if ( error )
+    {
+        goto Exit;
+    }
+
+    /*
+    Add the alternative glyph forms that come from features using
+    type 3 lookups.
+    This file from gtk was very useful in figuring out my approach:
+    
https://github.com/val-verde/gtk/blob/212e85e92628eda9f9650e5cc8d88c44062642ae/gtk/gtkfontchooserwidget.c#L2085
+    */
+    /*list of features containing type 3 lookups:*/
+    hb_tag_t feature_list[] = {
+        HB_TAG('s','a','l','t'),
+        HB_TAG('s','w','s','h'),
+        HB_TAG('n','a','l','t'),
+        HB_TAG_NONE
+    };
+
+
+    hb_ot_layout_collect_lookups ( hb_face,
+                                   HB_OT_TAG_GSUB,
+                                   NULL,
+                                   NULL,
+                                   feature_list,
+                                   type_3_lookup_indicies);
+
+    if ( !hb_set_allocation_successful( type_3_lookup_indicies ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto Exit;
+    }
+
+    if (( error = FT_NEW_ARRAY( type_3_alternate_glyphs_buffer, 100 ) ))
+    {
+        goto Exit;
+    }
+    hb_codepoint_t lookup_index = HB_SET_VALUE_INVALID;
+    FT_UInt base_glyph_index = FT_Get_Char_Index( face, codepoint );
+    if ( base_glyph_index != 0 ) {
+        while ( hb_set_next( type_3_lookup_indicies, &lookup_index ) )
+        {
+            unsigned alternate_count = 100;
+
+            hb_ot_layout_lookup_get_glyph_alternates
+                                        ( hb_face,
+                                          lookup_index,
+                                          base_glyph_index,
+                                          0,
+                                          &alternate_count,
+                                          type_3_alternate_glyphs_buffer );
+
+            for ( unsigned i = 0; i < alternate_count; i++ )
+            {
+                hb_set_add( result, type_3_alternate_glyphs_buffer[i] );
+            }
+        }
+    }
+
+
+
+Exit:
+    hb_set_destroy( feature_tags );
+    hb_buffer_destroy( codepoint_buffer );
+    FT_FREE( feature_buffer );
+    FT_FREE( type_3_alternate_glyphs_buffer );
+    return error;
+}
+#endif /*FT_CONFIG_OPTION_USE_HARFBUZZ*/
+
 FT_LOCAL_DEF( FT_Error )
 af_reverse_character_map_new( AF_ReverseCharacterMap *map, AF_FaceGlobals 
globals )
 {
@@ -303,6 +613,54 @@ af_reverse_character_map_new( AF_ReverseCharacterMap *map, 
AF_FaceGlobals global
     {
         goto Exit;
     }
+#ifdef FT_CONFIG_OPTION_USE_HARFBUZZ
+    hb_font_t *hb_font = globals->hb_font;
+    /*hb_face_t *hb_face = hb_font_get_face( hb_font );*/
+    hb_set_t *result_set = hb_set_create();
+    if ( !hb_set_allocation_successful( result_set ) )
+    {
+        error = FT_Err_Out_Of_Memory;
+        goto harfbuzz_path_Exit;
+    }
+
+    /*find alll glyph variants of the codepoints, then make an entry from
+    the glyph to the codepoint for each one*/
+    for ( FT_Long i = 0; i < AF_ADJUSTMENT_DATABASE_LENGTH; i++ )
+    {
+        FT_UInt32 codepoint = adjustment_database[i].codepoint;
+
+        error = af_all_glyph_variants( face,
+                                       hb_font,
+                                       codepoint,
+                                       result_set );
+        if ( error )
+        {
+            goto harfbuzz_path_Exit;
+        }
+
+        hb_codepoint_t glyph = HB_SET_VALUE_INVALID;
+        while ( hb_set_next( result_set, &glyph ) )
+        {
+            error = af_reverse_character_map_expand( *map, &capacity, memory );
+            if ( error ) {
+                goto harfbuzz_path_Exit;
+            }
+
+            FT_Long insert_point = ( *map )->length;
+            ( *map )->length++;
+            ( *map )->entries[insert_point].glyph_index = glyph;
+            ( *map )->entries[insert_point].codepoint = codepoint;
+        }
+
+        hb_set_clear( result_set );
+    }
+harfbuzz_path_Exit:
+    hb_set_destroy( result_set );
+    if ( error )
+    {
+        goto Exit;
+    }
+#else /* !FT_CONFIG_OPTION_USE_HARFBUZZ */
 
 #ifdef FT_DEBUG_LEVEL_TRACE
     int failed_lookups = 0;
@@ -328,6 +686,8 @@ af_reverse_character_map_new( AF_ReverseCharacterMap *map, 
AF_FaceGlobals global
         ( *map )->entries[i].codepoint = codepoint;
     }
 
+#endif /*FT_CONFIG_OPTION_USE_HARFBUZZ*/
+
     ft_qsort(
         ( *map )->entries,
         ( *map )->length,