xref: /aosp_15_r20/external/fonttools/Lib/fontTools/varLib/featureVars.py (revision e1fe3e4ad2793916b15cccdc4a7da52a7e1dd0e9)
1"""Module to build FeatureVariation tables:
2https://docs.microsoft.com/en-us/typography/opentype/spec/chapter2#featurevariations-table
3
4NOTE: The API is experimental and subject to change.
5"""
6
7from fontTools.misc.dictTools import hashdict
8from fontTools.misc.intTools import bit_count
9from fontTools.ttLib import newTable
10from fontTools.ttLib.tables import otTables as ot
11from fontTools.ttLib.ttVisitor import TTVisitor
12from fontTools.otlLib.builder import buildLookup, buildSingleSubstSubtable
13from collections import OrderedDict
14
15from .errors import VarLibError, VarLibValidationError
16
17
18def addFeatureVariations(font, conditionalSubstitutions, featureTag="rvrn"):
19    """Add conditional substitutions to a Variable Font.
20
21    The `conditionalSubstitutions` argument is a list of (Region, Substitutions)
22    tuples.
23
24    A Region is a list of Boxes. A Box is a dict mapping axisTags to
25    (minValue, maxValue) tuples. Irrelevant axes may be omitted and they are
26    interpretted as extending to end of axis in each direction.  A Box represents
27    an orthogonal 'rectangular' subset of an N-dimensional design space.
28    A Region represents a more complex subset of an N-dimensional design space,
29    ie. the union of all the Boxes in the Region.
30    For efficiency, Boxes within a Region should ideally not overlap, but
31    functionality is not compromised if they do.
32
33    The minimum and maximum values are expressed in normalized coordinates.
34
35    A Substitution is a dict mapping source glyph names to substitute glyph names.
36
37    Example:
38
39    # >>> f = TTFont(srcPath)
40    # >>> condSubst = [
41    # ...     # A list of (Region, Substitution) tuples.
42    # ...     ([{"wdth": (0.5, 1.0)}], {"cent": "cent.rvrn"}),
43    # ...     ([{"wght": (0.5, 1.0)}], {"dollar": "dollar.rvrn"}),
44    # ... ]
45    # >>> addFeatureVariations(f, condSubst)
46    # >>> f.save(dstPath)
47
48    The `featureTag` parameter takes either a str or a iterable of str (the single str
49    is kept for backwards compatibility), and defines which feature(s) will be
50    associated with the feature variations.
51    Note, if this is "rvrn", then the substitution lookup will be inserted at the
52    beginning of the lookup list so that it is processed before others, otherwise
53    for any other feature tags it will be appended last.
54    """
55
56    # process first when "rvrn" is the only listed tag
57    featureTags = [featureTag] if isinstance(featureTag, str) else sorted(featureTag)
58    processLast = "rvrn" not in featureTags or len(featureTags) > 1
59
60    _checkSubstitutionGlyphsExist(
61        glyphNames=set(font.getGlyphOrder()),
62        substitutions=conditionalSubstitutions,
63    )
64
65    substitutions = overlayFeatureVariations(conditionalSubstitutions)
66
67    # turn substitution dicts into tuples of tuples, so they are hashable
68    conditionalSubstitutions, allSubstitutions = makeSubstitutionsHashable(
69        substitutions
70    )
71    if "GSUB" not in font:
72        font["GSUB"] = buildGSUB()
73    else:
74        existingTags = _existingVariableFeatures(font["GSUB"].table).intersection(
75            featureTags
76        )
77        if existingTags:
78            raise VarLibError(
79                f"FeatureVariations already exist for feature tag(s): {existingTags}"
80            )
81
82    # setup lookups
83    lookupMap = buildSubstitutionLookups(
84        font["GSUB"].table, allSubstitutions, processLast
85    )
86
87    # addFeatureVariationsRaw takes a list of
88    #  ( {condition}, [ lookup indices ] )
89    # so rearrange our lookups to match
90    conditionsAndLookups = []
91    for conditionSet, substitutions in conditionalSubstitutions:
92        conditionsAndLookups.append(
93            (conditionSet, [lookupMap[s] for s in substitutions])
94        )
95
96    addFeatureVariationsRaw(font, font["GSUB"].table, conditionsAndLookups, featureTags)
97
98
99def _existingVariableFeatures(table):
100    existingFeatureVarsTags = set()
101    if hasattr(table, "FeatureVariations") and table.FeatureVariations is not None:
102        features = table.FeatureList.FeatureRecord
103        for fvr in table.FeatureVariations.FeatureVariationRecord:
104            for ftsr in fvr.FeatureTableSubstitution.SubstitutionRecord:
105                existingFeatureVarsTags.add(features[ftsr.FeatureIndex].FeatureTag)
106    return existingFeatureVarsTags
107
108
109def _checkSubstitutionGlyphsExist(glyphNames, substitutions):
110    referencedGlyphNames = set()
111    for _, substitution in substitutions:
112        referencedGlyphNames |= substitution.keys()
113        referencedGlyphNames |= set(substitution.values())
114    missing = referencedGlyphNames - glyphNames
115    if missing:
116        raise VarLibValidationError(
117            "Missing glyphs are referenced in conditional substitution rules:"
118            f" {', '.join(missing)}"
119        )
120
121
122def overlayFeatureVariations(conditionalSubstitutions):
123    """Compute overlaps between all conditional substitutions.
124
125    The `conditionalSubstitutions` argument is a list of (Region, Substitutions)
126    tuples.
127
128    A Region is a list of Boxes. A Box is a dict mapping axisTags to
129    (minValue, maxValue) tuples. Irrelevant axes may be omitted and they are
130    interpretted as extending to end of axis in each direction.  A Box represents
131    an orthogonal 'rectangular' subset of an N-dimensional design space.
132    A Region represents a more complex subset of an N-dimensional design space,
133    ie. the union of all the Boxes in the Region.
134    For efficiency, Boxes within a Region should ideally not overlap, but
135    functionality is not compromised if they do.
136
137    The minimum and maximum values are expressed in normalized coordinates.
138
139    A Substitution is a dict mapping source glyph names to substitute glyph names.
140
141    Returns data is in similar but different format.  Overlaps of distinct
142    substitution Boxes (*not* Regions) are explicitly listed as distinct rules,
143    and rules with the same Box merged.  The more specific rules appear earlier
144    in the resulting list.  Moreover, instead of just a dictionary of substitutions,
145    a list of dictionaries is returned for substitutions corresponding to each
146    unique space, with each dictionary being identical to one of the input
147    substitution dictionaries.  These dictionaries are not merged to allow data
148    sharing when they are converted into font tables.
149
150    Example::
151
152        >>> condSubst = [
153        ...     # A list of (Region, Substitution) tuples.
154        ...     ([{"wght": (0.5, 1.0)}], {"dollar": "dollar.rvrn"}),
155        ...     ([{"wght": (0.5, 1.0)}], {"dollar": "dollar.rvrn"}),
156        ...     ([{"wdth": (0.5, 1.0)}], {"cent": "cent.rvrn"}),
157        ...     ([{"wght": (0.5, 1.0), "wdth": (-1, 1.0)}], {"dollar": "dollar.rvrn"}),
158        ... ]
159        >>> from pprint import pprint
160        >>> pprint(overlayFeatureVariations(condSubst))
161        [({'wdth': (0.5, 1.0), 'wght': (0.5, 1.0)},
162          [{'dollar': 'dollar.rvrn'}, {'cent': 'cent.rvrn'}]),
163         ({'wdth': (0.5, 1.0)}, [{'cent': 'cent.rvrn'}]),
164         ({'wght': (0.5, 1.0)}, [{'dollar': 'dollar.rvrn'}])]
165
166    """
167
168    # Merge same-substitutions rules, as this creates fewer number oflookups.
169    merged = OrderedDict()
170    for value, key in conditionalSubstitutions:
171        key = hashdict(key)
172        if key in merged:
173            merged[key].extend(value)
174        else:
175            merged[key] = value
176    conditionalSubstitutions = [(v, dict(k)) for k, v in merged.items()]
177    del merged
178
179    # Merge same-region rules, as this is cheaper.
180    # Also convert boxes to hashdict()
181    #
182    # Reversing is such that earlier entries win in case of conflicting substitution
183    # rules for the same region.
184    merged = OrderedDict()
185    for key, value in reversed(conditionalSubstitutions):
186        key = tuple(
187            sorted(
188                (hashdict(cleanupBox(k)) for k in key),
189                key=lambda d: tuple(sorted(d.items())),
190            )
191        )
192        if key in merged:
193            merged[key].update(value)
194        else:
195            merged[key] = dict(value)
196    conditionalSubstitutions = list(reversed(merged.items()))
197    del merged
198
199    # Overlay
200    #
201    # Rank is the bit-set of the index of all contributing layers.
202    initMapInit = ((hashdict(), 0),)  # Initializer representing the entire space
203    boxMap = OrderedDict(initMapInit)  # Map from Box to Rank
204    for i, (currRegion, _) in enumerate(conditionalSubstitutions):
205        newMap = OrderedDict(initMapInit)
206        currRank = 1 << i
207        for box, rank in boxMap.items():
208            for currBox in currRegion:
209                intersection, remainder = overlayBox(currBox, box)
210                if intersection is not None:
211                    intersection = hashdict(intersection)
212                    newMap[intersection] = newMap.get(intersection, 0) | rank | currRank
213                if remainder is not None:
214                    remainder = hashdict(remainder)
215                    newMap[remainder] = newMap.get(remainder, 0) | rank
216        boxMap = newMap
217
218    # Generate output
219    items = []
220    for box, rank in sorted(
221        boxMap.items(), key=(lambda BoxAndRank: -bit_count(BoxAndRank[1]))
222    ):
223        # Skip any box that doesn't have any substitution.
224        if rank == 0:
225            continue
226        substsList = []
227        i = 0
228        while rank:
229            if rank & 1:
230                substsList.append(conditionalSubstitutions[i][1])
231            rank >>= 1
232            i += 1
233        items.append((dict(box), substsList))
234    return items
235
236
237#
238# Terminology:
239#
240# A 'Box' is a dict representing an orthogonal "rectangular" bit of N-dimensional space.
241# The keys in the dict are axis tags, the values are (minValue, maxValue) tuples.
242# Missing dimensions (keys) are substituted by the default min and max values
243# from the corresponding axes.
244#
245
246
247def overlayBox(top, bot):
248    """Overlays ``top`` box on top of ``bot`` box.
249
250    Returns two items:
251
252    * Box for intersection of ``top`` and ``bot``, or None if they don't intersect.
253    * Box for remainder of ``bot``.  Remainder box might not be exact (since the
254      remainder might not be a simple box), but is inclusive of the exact
255      remainder.
256    """
257
258    # Intersection
259    intersection = {}
260    intersection.update(top)
261    intersection.update(bot)
262    for axisTag in set(top) & set(bot):
263        min1, max1 = top[axisTag]
264        min2, max2 = bot[axisTag]
265        minimum = max(min1, min2)
266        maximum = min(max1, max2)
267        if not minimum < maximum:
268            return None, bot  # Do not intersect
269        intersection[axisTag] = minimum, maximum
270
271    # Remainder
272    #
273    # Remainder is empty if bot's each axis range lies within that of intersection.
274    #
275    # Remainder is shrank if bot's each, except for exactly one, axis range lies
276    # within that of intersection, and that one axis, it extrudes out of the
277    # intersection only on one side.
278    #
279    # Bot is returned in full as remainder otherwise, as true remainder is not
280    # representable as a single box.
281
282    remainder = dict(bot)
283    extruding = False
284    fullyInside = True
285    for axisTag in top:
286        if axisTag in bot:
287            continue
288        extruding = True
289        fullyInside = False
290        break
291    for axisTag in bot:
292        if axisTag not in top:
293            continue  # Axis range lies fully within
294        min1, max1 = intersection[axisTag]
295        min2, max2 = bot[axisTag]
296        if min1 <= min2 and max2 <= max1:
297            continue  # Axis range lies fully within
298
299        # Bot's range doesn't fully lie within that of top's for this axis.
300        # We know they intersect, so it cannot lie fully without either; so they
301        # overlap.
302
303        # If we have had an overlapping axis before, remainder is not
304        # representable as a box, so return full bottom and go home.
305        if extruding:
306            return intersection, bot
307        extruding = True
308        fullyInside = False
309
310        # Otherwise, cut remainder on this axis and continue.
311        if min1 <= min2:
312            # Right side survives.
313            minimum = max(max1, min2)
314            maximum = max2
315        elif max2 <= max1:
316            # Left side survives.
317            minimum = min2
318            maximum = min(min1, max2)
319        else:
320            # Remainder leaks out from both sides.  Can't cut either.
321            return intersection, bot
322
323        remainder[axisTag] = minimum, maximum
324
325    if fullyInside:
326        # bot is fully within intersection.  Remainder is empty.
327        return intersection, None
328
329    return intersection, remainder
330
331
332def cleanupBox(box):
333    """Return a sparse copy of `box`, without redundant (default) values.
334
335    >>> cleanupBox({})
336    {}
337    >>> cleanupBox({'wdth': (0.0, 1.0)})
338    {'wdth': (0.0, 1.0)}
339    >>> cleanupBox({'wdth': (-1.0, 1.0)})
340    {}
341
342    """
343    return {tag: limit for tag, limit in box.items() if limit != (-1.0, 1.0)}
344
345
346#
347# Low level implementation
348#
349
350
351def addFeatureVariationsRaw(font, table, conditionalSubstitutions, featureTag="rvrn"):
352    """Low level implementation of addFeatureVariations that directly
353    models the possibilities of the FeatureVariations table."""
354
355    featureTags = [featureTag] if isinstance(featureTag, str) else sorted(featureTag)
356    processLast = "rvrn" not in featureTags or len(featureTags) > 1
357
358    #
359    # if a <featureTag> feature is not present:
360    #     make empty <featureTag> feature
361    #     sort features, get <featureTag> feature index
362    #     add <featureTag> feature to all scripts
363    # if a <featureTag> feature is present:
364    #     reuse <featureTag> feature index
365    # make lookups
366    # add feature variations
367    #
368    if table.Version < 0x00010001:
369        table.Version = 0x00010001  # allow table.FeatureVariations
370
371    varFeatureIndices = set()
372
373    existingTags = {
374        feature.FeatureTag
375        for feature in table.FeatureList.FeatureRecord
376        if feature.FeatureTag in featureTags
377    }
378
379    newTags = set(featureTags) - existingTags
380    if newTags:
381        varFeatures = []
382        for featureTag in sorted(newTags):
383            varFeature = buildFeatureRecord(featureTag, [])
384            table.FeatureList.FeatureRecord.append(varFeature)
385            varFeatures.append(varFeature)
386        table.FeatureList.FeatureCount = len(table.FeatureList.FeatureRecord)
387
388        sortFeatureList(table)
389
390        for varFeature in varFeatures:
391            varFeatureIndex = table.FeatureList.FeatureRecord.index(varFeature)
392
393            for scriptRecord in table.ScriptList.ScriptRecord:
394                if scriptRecord.Script.DefaultLangSys is None:
395                    raise VarLibError(
396                        "Feature variations require that the script "
397                        f"'{scriptRecord.ScriptTag}' defines a default language system."
398                    )
399                langSystems = [lsr.LangSys for lsr in scriptRecord.Script.LangSysRecord]
400                for langSys in [scriptRecord.Script.DefaultLangSys] + langSystems:
401                    langSys.FeatureIndex.append(varFeatureIndex)
402                    langSys.FeatureCount = len(langSys.FeatureIndex)
403            varFeatureIndices.add(varFeatureIndex)
404
405    if existingTags:
406        # indices may have changed if we inserted new features and sorted feature list
407        # so we must do this after the above
408        varFeatureIndices.update(
409            index
410            for index, feature in enumerate(table.FeatureList.FeatureRecord)
411            if feature.FeatureTag in existingTags
412        )
413
414    axisIndices = {
415        axis.axisTag: axisIndex for axisIndex, axis in enumerate(font["fvar"].axes)
416    }
417
418    hasFeatureVariations = (
419        hasattr(table, "FeatureVariations") and table.FeatureVariations is not None
420    )
421
422    featureVariationRecords = []
423    for conditionSet, lookupIndices in conditionalSubstitutions:
424        conditionTable = []
425        for axisTag, (minValue, maxValue) in sorted(conditionSet.items()):
426            if minValue > maxValue:
427                raise VarLibValidationError(
428                    "A condition set has a minimum value above the maximum value."
429                )
430            ct = buildConditionTable(axisIndices[axisTag], minValue, maxValue)
431            conditionTable.append(ct)
432        records = []
433        for varFeatureIndex in sorted(varFeatureIndices):
434            existingLookupIndices = table.FeatureList.FeatureRecord[
435                varFeatureIndex
436            ].Feature.LookupListIndex
437            combinedLookupIndices = (
438                existingLookupIndices + lookupIndices
439                if processLast
440                else lookupIndices + existingLookupIndices
441            )
442
443            records.append(
444                buildFeatureTableSubstitutionRecord(
445                    varFeatureIndex, combinedLookupIndices
446                )
447            )
448        if hasFeatureVariations and (
449            fvr := findFeatureVariationRecord(table.FeatureVariations, conditionTable)
450        ):
451            fvr.FeatureTableSubstitution.SubstitutionRecord.extend(records)
452            fvr.FeatureTableSubstitution.SubstitutionCount = len(
453                fvr.FeatureTableSubstitution.SubstitutionRecord
454            )
455        else:
456            featureVariationRecords.append(
457                buildFeatureVariationRecord(conditionTable, records)
458            )
459
460    if hasFeatureVariations:
461        if table.FeatureVariations.Version != 0x00010000:
462            raise VarLibError(
463                "Unsupported FeatureVariations table version: "
464                f"0x{table.FeatureVariations.Version:08x} (expected 0x00010000)."
465            )
466        table.FeatureVariations.FeatureVariationRecord.extend(featureVariationRecords)
467        table.FeatureVariations.FeatureVariationCount = len(
468            table.FeatureVariations.FeatureVariationRecord
469        )
470    else:
471        table.FeatureVariations = buildFeatureVariations(featureVariationRecords)
472
473
474#
475# Building GSUB/FeatureVariations internals
476#
477
478
479def buildGSUB():
480    """Build a GSUB table from scratch."""
481    fontTable = newTable("GSUB")
482    gsub = fontTable.table = ot.GSUB()
483    gsub.Version = 0x00010001  # allow gsub.FeatureVariations
484
485    gsub.ScriptList = ot.ScriptList()
486    gsub.ScriptList.ScriptRecord = []
487    gsub.FeatureList = ot.FeatureList()
488    gsub.FeatureList.FeatureRecord = []
489    gsub.LookupList = ot.LookupList()
490    gsub.LookupList.Lookup = []
491
492    srec = ot.ScriptRecord()
493    srec.ScriptTag = "DFLT"
494    srec.Script = ot.Script()
495    srec.Script.DefaultLangSys = None
496    srec.Script.LangSysRecord = []
497    srec.Script.LangSysCount = 0
498
499    langrec = ot.LangSysRecord()
500    langrec.LangSys = ot.LangSys()
501    langrec.LangSys.ReqFeatureIndex = 0xFFFF
502    langrec.LangSys.FeatureIndex = []
503    srec.Script.DefaultLangSys = langrec.LangSys
504
505    gsub.ScriptList.ScriptRecord.append(srec)
506    gsub.ScriptList.ScriptCount = 1
507    gsub.FeatureVariations = None
508
509    return fontTable
510
511
512def makeSubstitutionsHashable(conditionalSubstitutions):
513    """Turn all the substitution dictionaries in sorted tuples of tuples so
514    they are hashable, to detect duplicates so we don't write out redundant
515    data."""
516    allSubstitutions = set()
517    condSubst = []
518    for conditionSet, substitutionMaps in conditionalSubstitutions:
519        substitutions = []
520        for substitutionMap in substitutionMaps:
521            subst = tuple(sorted(substitutionMap.items()))
522            substitutions.append(subst)
523            allSubstitutions.add(subst)
524        condSubst.append((conditionSet, substitutions))
525    return condSubst, sorted(allSubstitutions)
526
527
528class ShifterVisitor(TTVisitor):
529    def __init__(self, shift):
530        self.shift = shift
531
532
533@ShifterVisitor.register_attr(ot.Feature, "LookupListIndex")  # GSUB/GPOS
534def visit(visitor, obj, attr, value):
535    shift = visitor.shift
536    value = [l + shift for l in value]
537    setattr(obj, attr, value)
538
539
540@ShifterVisitor.register_attr(
541    (ot.SubstLookupRecord, ot.PosLookupRecord), "LookupListIndex"
542)
543def visit(visitor, obj, attr, value):
544    setattr(obj, attr, visitor.shift + value)
545
546
547def buildSubstitutionLookups(gsub, allSubstitutions, processLast=False):
548    """Build the lookups for the glyph substitutions, return a dict mapping
549    the substitution to lookup indices."""
550
551    # Insert lookups at the beginning of the lookup vector
552    # https://github.com/googlefonts/fontmake/issues/950
553
554    firstIndex = len(gsub.LookupList.Lookup) if processLast else 0
555    lookupMap = {}
556    for i, substitutionMap in enumerate(allSubstitutions):
557        lookupMap[substitutionMap] = firstIndex + i
558
559    if not processLast:
560        # Shift all lookup indices in gsub by len(allSubstitutions)
561        shift = len(allSubstitutions)
562        visitor = ShifterVisitor(shift)
563        visitor.visit(gsub.FeatureList.FeatureRecord)
564        visitor.visit(gsub.LookupList.Lookup)
565
566    for i, subst in enumerate(allSubstitutions):
567        substMap = dict(subst)
568        lookup = buildLookup([buildSingleSubstSubtable(substMap)])
569        if processLast:
570            gsub.LookupList.Lookup.append(lookup)
571        else:
572            gsub.LookupList.Lookup.insert(i, lookup)
573        assert gsub.LookupList.Lookup[lookupMap[subst]] is lookup
574    gsub.LookupList.LookupCount = len(gsub.LookupList.Lookup)
575    return lookupMap
576
577
578def buildFeatureVariations(featureVariationRecords):
579    """Build the FeatureVariations subtable."""
580    fv = ot.FeatureVariations()
581    fv.Version = 0x00010000
582    fv.FeatureVariationRecord = featureVariationRecords
583    fv.FeatureVariationCount = len(featureVariationRecords)
584    return fv
585
586
587def buildFeatureRecord(featureTag, lookupListIndices):
588    """Build a FeatureRecord."""
589    fr = ot.FeatureRecord()
590    fr.FeatureTag = featureTag
591    fr.Feature = ot.Feature()
592    fr.Feature.LookupListIndex = lookupListIndices
593    fr.Feature.populateDefaults()
594    return fr
595
596
597def buildFeatureVariationRecord(conditionTable, substitutionRecords):
598    """Build a FeatureVariationRecord."""
599    fvr = ot.FeatureVariationRecord()
600    fvr.ConditionSet = ot.ConditionSet()
601    fvr.ConditionSet.ConditionTable = conditionTable
602    fvr.ConditionSet.ConditionCount = len(conditionTable)
603    fvr.FeatureTableSubstitution = ot.FeatureTableSubstitution()
604    fvr.FeatureTableSubstitution.Version = 0x00010000
605    fvr.FeatureTableSubstitution.SubstitutionRecord = substitutionRecords
606    fvr.FeatureTableSubstitution.SubstitutionCount = len(substitutionRecords)
607    return fvr
608
609
610def buildFeatureTableSubstitutionRecord(featureIndex, lookupListIndices):
611    """Build a FeatureTableSubstitutionRecord."""
612    ftsr = ot.FeatureTableSubstitutionRecord()
613    ftsr.FeatureIndex = featureIndex
614    ftsr.Feature = ot.Feature()
615    ftsr.Feature.LookupListIndex = lookupListIndices
616    ftsr.Feature.LookupCount = len(lookupListIndices)
617    return ftsr
618
619
620def buildConditionTable(axisIndex, filterRangeMinValue, filterRangeMaxValue):
621    """Build a ConditionTable."""
622    ct = ot.ConditionTable()
623    ct.Format = 1
624    ct.AxisIndex = axisIndex
625    ct.FilterRangeMinValue = filterRangeMinValue
626    ct.FilterRangeMaxValue = filterRangeMaxValue
627    return ct
628
629
630def findFeatureVariationRecord(featureVariations, conditionTable):
631    """Find a FeatureVariationRecord that has the same conditionTable."""
632    if featureVariations.Version != 0x00010000:
633        raise VarLibError(
634            "Unsupported FeatureVariations table version: "
635            f"0x{featureVariations.Version:08x} (expected 0x00010000)."
636        )
637
638    for fvr in featureVariations.FeatureVariationRecord:
639        if conditionTable == fvr.ConditionSet.ConditionTable:
640            return fvr
641
642    return None
643
644
645def sortFeatureList(table):
646    """Sort the feature list by feature tag, and remap the feature indices
647    elsewhere. This is needed after the feature list has been modified.
648    """
649    # decorate, sort, undecorate, because we need to make an index remapping table
650    tagIndexFea = [
651        (fea.FeatureTag, index, fea)
652        for index, fea in enumerate(table.FeatureList.FeatureRecord)
653    ]
654    tagIndexFea.sort()
655    table.FeatureList.FeatureRecord = [fea for tag, index, fea in tagIndexFea]
656    featureRemap = dict(
657        zip([index for tag, index, fea in tagIndexFea], range(len(tagIndexFea)))
658    )
659
660    # Remap the feature indices
661    remapFeatures(table, featureRemap)
662
663
664def remapFeatures(table, featureRemap):
665    """Go through the scripts list, and remap feature indices."""
666    for scriptIndex, script in enumerate(table.ScriptList.ScriptRecord):
667        defaultLangSys = script.Script.DefaultLangSys
668        if defaultLangSys is not None:
669            _remapLangSys(defaultLangSys, featureRemap)
670        for langSysRecordIndex, langSysRec in enumerate(script.Script.LangSysRecord):
671            langSys = langSysRec.LangSys
672            _remapLangSys(langSys, featureRemap)
673
674    if hasattr(table, "FeatureVariations") and table.FeatureVariations is not None:
675        for fvr in table.FeatureVariations.FeatureVariationRecord:
676            for ftsr in fvr.FeatureTableSubstitution.SubstitutionRecord:
677                ftsr.FeatureIndex = featureRemap[ftsr.FeatureIndex]
678
679
680def _remapLangSys(langSys, featureRemap):
681    if langSys.ReqFeatureIndex != 0xFFFF:
682        langSys.ReqFeatureIndex = featureRemap[langSys.ReqFeatureIndex]
683    langSys.FeatureIndex = [featureRemap[index] for index in langSys.FeatureIndex]
684
685
686if __name__ == "__main__":
687    import doctest, sys
688
689    sys.exit(doctest.testmod().failed)
690