DecomposeTransformedComponentsFilter: MM compatibility issues

[m4rc1e]

I've just come across a family which has an exclamdown which is constructed using a rotated exclam:

The exclam component for this glyph is constructed from both paths and components.

When the DecomposeTransformedComponentsFilter is run as a prefilter, the exclam is decomposed as one would expect.

However, when the filter decomposes the exclamdown, the path order differs.

Shotgun approaches to solve this issue are to run the filter as a post filter. This works because the exclam which has mixed paths and components will be decomposed first, https://github.com/googlefonts/ufo2ft/blob/main/Lib/ufo2ft/preProcessor.py#L337-L342. The other options is to move the https://github.com/googlefonts/ufo2ft/blob/main/Lib/ufo2ft/preProcessor.py#L337-L342 so it happens before the pre filters.

Here's a minimal testcase:
changa.zip

[anthrotype]

The order between components and contours is basically undefined in UFO spec: unified-font-object/ufo-spec#169
Accordingly when ufoLib parses a .glif file, it doesn't record the order in which contours and components are interspersed inside a glif's <outline> xml element; it simply appends all contours to Glyph.contours list and and all components to Glyph.components list, independently of one another. So we have no way to know whether a component comes before a contour or after.
The argument is it doesn't matter which one comes first because in nonzero fill rule the contour's winding direction is what matters (nor it matters in evenodd rule FWIW). However, there're situation when it does matter, like in our case when merging multiple master fonts in a variable font with fontTools.varLib and we need to decompose glyphs in a way that maintains point-to-point compatibility across masters. So we have to come up with our own way to sort through them and it has to be reliable, no matter what the configuration of the components is, how nested/transformed/mixed whatever they are..

The way ufo2ft.util.deepCopyContours (used by all the decomposing filters) works right now is: traverse the tree of components calling itself recursively and when you reach a leaf and can't go further, if there are contours, then draw those onto the root glyph (where you started the traversal) with some transformation (which is the concatenation of all the components' transforms found in the traversal so far). So this is a pre-order post-order, depth-first traversal, the children (of children of children) are visited (decomposed) first, then oneself.
For example, if the root glyph has a simple mix of contours and components which in turn are not "nested", and we ask ufo2ft to decompose it, it will end up with, first, all the contours kept as they were, then followed by all the components's contours in the order in which the components appear in the root glyph. So in the simplest scenario, all contours first then all components. This is what happens for the "exclam" glyph in the Changa-Regular.ufo: it has one contour (the vertical stem of the exclamation mark) and one component (a "period" offsetted by 10 units); after decomposition, it has two contours, the first hasn't changed, the second is the contour of the "period" glyph offsetted by 10 units. So far so good.
In the case of "exclamdown", we have one component "exclam" that has xScale=-1 and yScale=-1 (flipped both vertically and horizontally) so we our DecomposeTransformedComponents filter wants to decompose it because its 2x2 matrix is not Identity(1,0,0,1); but "exclam" glyph in turn contains both contours and components, and our deepCopyContours recursive algorithm above decides to first traverse the components and then draw any contours, so the "period"'s contour gets drawn before the vertical stem of the "exclam" glyph and we end up with a contour order in the decomposed "exclamdown" which is the reverse of the one we got for "exclam" in the previous example.

This should not matter because they are distinct glyphs in the end, we match each glyph to merge from each masters by their name, so as long as "exclam" and "exclamdown" have each respectively the same structure across masters, who cares that the contours are ordered differently betweem them.

But.. it turns out, in at least two of the three masters in the testcase (Bold and ExtraLight, but not Regular), the "exclam" composite glyph has a "period" component with a non-identity 2x2 transform (in Regular, it only has an offset), so in those two masters (but not in the third) it gets caught by the DecomposeTransformedComponents filter and decomposed.
Now the problem is, filters (including decomposing filters) modify each glyph in-place, and in the order in which they appear in the glyphOrder; exclam comes before exclamdown so, in two of the three masters (i.e. where it has a scale), it gets decomposed before "exclamdown" gets decomposed. By the time "exclamdown" is to be decomposed, it finds "exclam" (the same glyph, modified in-place) already decomposed so it simply draws its contours in that order; whereas, in one of the three masters (Regular), "exclam" only has a simple "period" with an offset (no 2x2 transform), so DecomposeTransformedComponents leaves it alone and turns to "exclamdown"; here it follows post-order DFS and decomposes the period before the rest of the "exclam" mixed composite and we finally end up with incompatible decomposed "exclamdown" between this master and the other two...

If you are still reading, congratulations.

[anthrotype]

(sorry, of course I meant post-order, not pre-order, edited post)

[anthrotype]

If we change the order in which we traverse the component tree and do a pre-order traversal, i.e. visiting each node before visiting its children, then this particular test case gets fixed, however I am still not sure this is the right fix in general.

diff --git a/Lib/ufo2ft/util.py b/Lib/ufo2ft/util.py
index 0a1511b..fad38e8 100644
--- a/Lib/ufo2ft/util.py
+++ b/Lib/ufo2ft/util.py
@@ -150,6 +150,20 @@ def deepCopyContours(
     None, decompose all components of a glyph unconditionally and completely. If
     passed, only completely decompose components whose baseGlyph is in the list.
     """
+    # Check if there are any contours to copy before instantiating pens.
+    if composite != parent and len(composite):
+        if transformation == Identity:
+            pen = parent.getPen()
+        else:
+            pen = TransformPen(parent.getPen(), transformation)
+            # if the transformation has a negative determinant, it will
+            # reverse the contour direction of the component
+            xx, xy, yx, yy = transformation[:4]
+            if xx * yy - xy * yx < 0:
+                pen = ReverseContourPen(pen)
+
+        for contour in composite:
+            contour.draw(pen)

     for nestedComponent in composite.components:
         # Because this function works recursively, test at each turn if we are going to
@@ -180,21 +194,6 @@ def deepCopyContours(
                 specificComponents=specificComponentsEffective,
             )

-    # Check if there are any contours to copy before instantiating pens.
-    if composite != parent and len(composite):
-        if transformation == Identity:
-            pen = parent.getPen()
-        else:
-            pen = TransformPen(parent.getPen(), transformation)
-            # if the transformation has a negative determinant, it will
-            # reverse the contour direction of the component
-            xx, xy, yx, yy = transformation[:4]
-            if xx * yy - xy * yx < 0:
-                pen = ReverseContourPen(pen)
-
-        for contour in composite:
-            contour.draw(pen)
-

 def makeUnicodeToGlyphNameMapping(font, glyphOrder=None):
     """Make a unicode: glyph name mapping for this glyph set (dict or Font).

[anthrotype]

filters (including decomposing filters) modify each glyph in-place, and in the order in which they appear in the glyphOrder

no actually, they are just sorted alphabetically, see

ufo2ft/Lib/ufo2ft/filters/base.py

Lines 190 to 191 in 42257bc

	# we sort the glyph names to make loop deterministic
	for glyphName in sorted(glyphSet.keys()):

Of course, the root of the problem is we are modifying the glyphSet we are iterating over, hence the order in which we iterate matters for operations like decomposing in which one glyph influence another; if we made a copy before applying the filter, and then collected the modified glyphs and only substituted them in the glyphSet after we have filtered them all, then we would not incur in this issue, as the reference glyphSet used for decomposing would be the original, unmodified one, before running the decomposing filter; thus, the glyph order in which perform decomposition would not matter.

However, making a copy of each glyph upfront, before knowing if it would be modified or not, would be quite inefficient.

diff --git a/Lib/ufo2ft/filters/base.py b/Lib/ufo2ft/filters/base.py
index 0286414..2bcd47c 100644
--- a/Lib/ufo2ft/filters/base.py
+++ b/Lib/ufo2ft/filters/base.py
@@ -3,7 +3,7 @@ from types import SimpleNamespace

 from fontTools.misc.loggingTools import Timer

-from ufo2ft.util import _GlyphSet, _LazyFontName
+from ufo2ft.util import _GlyphSet, _LazyFontName, _copyGlyph

 logger = logging.getLogger(__name__)

@@ -185,6 +185,7 @@ class BaseFilter:
         filter_ = self.filter
         include = self.include
         modified = context.modified
+        copies = {}

         with Timer() as t:
             # we sort the glyph names to make loop deterministic
@@ -192,11 +193,17 @@ class BaseFilter:
                 if glyphName in modified:
                     continue
                 glyph = glyphSet[glyphName]
-                if include(glyph) and filter_(glyph):
-                    modified.add(glyphName)
+                if include(glyph):
+                    copy = _copyGlyph(glyph)
+                    if filter_(copy):
+                        modified.add(glyphName)
+                        copies[glyphName] = copy

         num = len(modified)
         if num > 0:
+            for n in modified:
+                glyphSet[n] = copies[n]
+
             logger.debug(
                 "Took %.3fs to run %s on %d glyph%s",
                 t,

[khaledhosny]

Wasn't this (or some other form of it) something @simoncozens recently fixed?

[anthrotype]

no it's slightly different. #609 deals with ensuring that if a glyph was decomposed in some masters as result of DecomposeTransformedComponents filter, it is also decomposed in the rest of the masters as well. Here "exclamdown" is decomposed in all masters already at first pass, only that it gets different contour order because of <can't summarize it further>

[anthrotype]

another way to fix this would be to change the order in which glyphs are processed by decompose filter by processing the composites with greater depth first (exclamdown before exclam)

[khaledhosny]

I see. May be we should sort the glyphs based on their use as components. I think the anchor propagation or some other code does this kind of sorting.

[anthrotype]

... that way, we avoid the interference of decomposing a composite of lower depth before another of greater depth. If we assume there are no cycles (which would already be a font bug), composites with same depth can't reference one another.