Repository: googlefonts/ufo2ft
Pull request #829 (2024-04-08 15:39:15)

[BaseIFilter] use cache to avoid recursing too much when gathering locations from component glyphs
Some fonts have hundred of masters and many nested components, leading the `BaseIFilter.locationsFromComponentGlyphs` method to seemingly hang in a very deep recursion loop.
Adding a cache avoids re-doing the same work (of gathering locations of all nested components of a composite glyph) over and over again.


Patch:
diff --git a/Lib/ufo2ft/filters/base.py b/Lib/ufo2ft/filters/base.py
index e286b6c..ca5ef83 100644
--- a/Lib/ufo2ft/filters/base.py
+++ b/Lib/ufo2ft/filters/base.py
@@ -291,6 +291,10 @@ class BaseIFilter(BaseFilter):
             **kwargs,
         )
         self.context.modified = set()
+        # this is used to memoize locationsFromComponentGlyphs method below, to avoid
+        # redoing the same work over and over again (especially when font has loads of
+        # masters and many nested components).
+        self.context.componentLocations = {}
         proto = fonts[0].layers.defaultLayer.instantiateGlyphObject()
         self.context.glyphFactory = _getNewGlyphFactory(proto)
         return self.context
@@ -427,16 +431,27 @@ class BaseIFilter(BaseFilter):
         include: set[str] | None = None,
     ) -> set[HashableLocation]:
         """Return locations from all the components' base glyphs, recursively."""
+        logger.debug("Gathering all locations from component glyphs: %s", glyphName)
         assert self.context.instantiator is not None
         locations = set()
+        cache = self.context.componentLocations
         for glyphSet in self.context.glyphSets:
             if glyphName in glyphSet:
                 glyph = glyphSet[glyphName]
                 for component in glyph.components:
-                    if include is None or component.baseGlyph in include:
-                        locations |= self.glyphSourceLocations(component.baseGlyph)
-                        locations |= self.locationsFromComponentGlyphs(
-                            component.baseGlyph, include
+                    baseGlyph = component.baseGlyph
+                    if include is None or baseGlyph in include:
+                        locations |= self.glyphSourceLocations(baseGlyph)
+                        # using ternary operator instead of cache.setdefault because
+                        # the latter always evaluates the second argument, whereas
+                        # I want it to be lazy to avoid recursing too often.
+                        locations |= (
+                            cache[baseGlyph]
+                            if baseGlyph in cache
+                            else cache.setdefault(
+                                baseGlyph,
+                                self.locationsFromComponentGlyphs(baseGlyph, include),
+                            )
                         )
         return locations
 
@@ -462,4 +477,9 @@ class BaseIFilter(BaseFilter):
             ):
                 if self.hashableLocation(interpolatedLayer.location) in locationsToAdd:
                     assert glyphName not in glyphSet
+                    logger.debug(
+                        "Interpolating composite glyph %r at %s",
+                        glyphName,
+                        interpolatedLayer.location,
+                    )
                     glyphSet[glyphName] = interpolatedLayer[glyphName]


Test patch:
diff --git a/tests/filters/decomposeComponents_test.py b/tests/filters/decomposeComponents_test.py
index 1d0bbce..6fce03e 100644
--- a/tests/filters/decomposeComponents_test.py
+++ b/tests/filters/decomposeComponents_test.py
@@ -1,3 +1,5 @@
+import logging
+
 import pytest
 from fontTools.pens.basePen import MissingComponentError
 
@@ -318,3 +320,52 @@ class DecomposeComponentsIFilterTest:
         modified = DecomposeComponentsIFilter(include={"igrave"})(ufos, glyphSets)
         assert modified == {"igrave"}
         assert "igrave" not in medium_glyphs
+
+    def test_locations_from_component_glyphs_get_cached(
+        self, caplog, ufos_and_glyphSets
+    ):
+        ufos, glyphSets = ufos_and_glyphSets
+        regular_glyphs, medium_glyphs, bold_glyphs = glyphSets
+        instantiator = Instantiator(
+            {"Weight": (100, 100, 200)},
+            [
+                ({"Weight": 100}, regular_glyphs),
+                ({"Weight": 150}, medium_glyphs),
+                ({"Weight": 200}, bold_glyphs),
+            ],
+        )
+        philter = DecomposeComponentsIFilter()
+        philter.set_context(ufos, glyphSets, instantiator)
+
+        igrave_locations = philter.glyphSourceLocations("igrave")
+
+        # igrave is defined only at Weight 100 and 200
+        assert igrave_locations == {
+            frozenset({("Weight", 100)}),
+            frozenset({("Weight", 200)}),
+        }
+
+        # locationsFromComponentGlyphs logs DEBUG messages while traversing
+        # recursively each component glyph
+        with caplog.at_level(logging.DEBUG, logger="ufo2ft.filters"):
+            component_locations = philter.locationsFromComponentGlyphs("igrave")
+
+        assert "igrave" in caplog.text
+        assert "dotlessi" in caplog.text
+        assert "gravecomb" in caplog.text
+
+        # one of igrave's components (dotlessi) is also defined at Weight 150
+        expected_component_locations = igrave_locations | {frozenset({("Weight", 150)})}
+        assert component_locations == expected_component_locations
+
+        # locationsFromComponentGlyphs uses a cache to avoid traversing again component
+        # glyphs that were visited before; its result isn't expected to change within
+        # the current filter call.
+        caplog.clear()
+        with caplog.at_level(logging.DEBUG, logger="ufo2ft.filters"):
+            component_locations = philter.locationsFromComponentGlyphs("igrave")
+
+        assert "igrave" in caplog.text
+        assert "dotlessi" not in caplog.text
+        assert "gravecomb" not in caplog.text
+        assert component_locations == expected_component_locations