Add Better Support for Cycle Detection for Font Fallback (SDL3)

[marinarasub]

With the current UpdateFontText(), it's still possible to get stuck in a cycle if there exists a fallback cycle that does not include the initial font given. In my case, I find a fix would be helpful for more complex multilingual interfaces (i.e. parts of interface are in a fixed language, but you can change the general interface language) as the fallback graph will tend to get quite complex.

Below is a basic implementation using TTF_FontList and calloc. Probably can optimize temporary memory allocations if it's necessary using an arena allocator or something similar.

Edit: Maybe a better option is for a fallback not to follow it's fallbacks, as the current font may want to ignore the fallback's fallback or at least in a different order

static void UpdateFontTextWithLoopDetection(TTF_Font *font, TTF_FontList** ret_visited)
{
    TTF_FontList* visited = *ret_visited;
    if (!visited) {
        visited = SDL_calloc(1, sizeof(TTF_FontList));
        visited->font = font;
        *ret_visited = visited;
    } else {
        TTF_FontList* visited_prev = NULL;
        for (TTF_FontList* visited_curr = visited; visited_curr; visited_prev = visited_curr, visited_curr = visited_curr->next) {
            if (visited_curr->font == font) {
                return;
            }
        }
        visited_prev->next = SDL_calloc(1, sizeof(TTF_FontList));
        visited_prev->next->font = font;
    }

    if (font->text) {
        SDL_IterateHashTable(font->text, UpdateFontTextCallback, NULL);
    }

    for (TTF_FontList *list = font->fallback_for; list; list = list->next) {
        UpdateFontTextWithLoopDetection(list->font, ret_visited);
    }
}

static void UpdateFontText(TTF_Font *font, TTF_Font *initial_font)
{
    TTF_FontList *visited = NULL;
    UpdateFontTextWithLoopDetection(font, &visited);
    while (visited) {
        TTF_FontList *visited_next = visited->next;
        SDL_free(visited);
        visited = visited_next;
    }
}

// current implementation:
// static void UpdateFontText(TTF_Font *font, TTF_Font *initial_font)
// {
//     if (!initial_font) {
//         initial_font = font;
//     } else if (font == initial_font) {
//         // font fallback loop
//         return;
//     }

//     if (font->text) {
//         SDL_IterateHashTable(font->text, UpdateFontTextCallback, NULL);
//     }

//     for (TTF_FontList *list = font->fallback_for; list; list = list->next) {
//         UpdateFontText(list->font, initial_font);
//     }
// }

[slouken]

Maybe it's better to just add a 'visited' flag in the font? It's not thread-safe, but avoids lots of allocation and list maintenance.

[marinarasub]

Yeah, that's probably a better idea. I guess you mean something simple like

static void UpdateFontText(TTF_Font *font, TTF_Font *initial_font)
{
    if (font->visited) {
        return;
    }
    font->visited = true;

    if (font->text) {
        SDL_IterateHashTable(font->text, UpdateFontTextCallback, NULL);
    }

    for (TTF_FontList *list = font->fallback_for; list; list = list->next) {
        UpdateFontText(list->font, initial_font);
    }

    font->visited = false;
}

I didn't have an issue with cycles with any other function, but I assume that's because every character I rendered had a glyph in one of the fonts. Assuming we also want to add cycle checking to all other functions which use fallbacks, potential issues might be for re-entrant uses of the flag, as well as non-pure function calls since I believe we'd technically be tracking the path as opposed to visited which means some fallbacks could be visited more than once. I'm guessing we're okay for both of those? Is there anything else to consider?

I think a single level of fallback could be much easier to maintain and have the added bonus of giving the user more flexibility and make fallback choice more explicit, but as a behaviour change I guess that'd have to be for the next major version (unless you add a separate type of fallback - perhaps you can also add an option for fallback and if toggled, don't follow if current font != initial_font)?