Coverage for /usr/lib/python3/dist-packages/fontTools/otlLib/optimize/gpos.py: 20%

1import logging

2import os

3from collections import defaultdict, namedtuple

4from functools import reduce

5from itertools import chain

6from math import log2

7from typing import DefaultDict, Dict, Iterable, List, Sequence, Tuple

9from fontTools.config import OPTIONS

10from fontTools.misc.intTools import bit_count, bit_indices

11from fontTools.ttLib import TTFont

12from fontTools.ttLib.tables import otBase, otTables

14log = logging.getLogger(__name__)

16COMPRESSION_LEVEL = OPTIONS[f"{__name__}:COMPRESSION_LEVEL"]

18# Kept because ufo2ft depends on it, to be removed once ufo2ft uses the config instead

19# https://github.com/fonttools/fonttools/issues/2592

20GPOS_COMPACT_MODE_ENV_KEY = "FONTTOOLS_GPOS_COMPACT_MODE"

21GPOS_COMPACT_MODE_DEFAULT = str(COMPRESSION_LEVEL.default)

24def _compression_level_from_env() -> int:

25 env_level = GPOS_COMPACT_MODE_DEFAULT

26 if GPOS_COMPACT_MODE_ENV_KEY in os.environ:

27 import warnings

29 warnings.warn(

30 f"'{GPOS_COMPACT_MODE_ENV_KEY}' environment variable is deprecated. "

31 "Please set the 'fontTools.otlLib.optimize.gpos:COMPRESSION_LEVEL' option "

32 "in TTFont.cfg.",

33 DeprecationWarning,

34 )

36 env_level = os.environ[GPOS_COMPACT_MODE_ENV_KEY]

37 if len(env_level) == 1 and env_level in "0123456789":

38 return int(env_level)

39 raise ValueError(f"Bad {GPOS_COMPACT_MODE_ENV_KEY}={env_level}")

42def compact(font: TTFont, level: int) -> TTFont:

43 # Ideal plan:

44 # 1. Find lookups of Lookup Type 2: Pair Adjustment Positioning Subtable

45 # https://docs.microsoft.com/en-us/typography/opentype/spec/gpos#lookup-type-2-pair-adjustment-positioning-subtable

46 # 2. Extract glyph-glyph kerning and class-kerning from all present subtables

47 # 3. Regroup into different subtable arrangements

48 # 4. Put back into the lookup

49 #

50 # Actual implementation:

51 # 2. Only class kerning is optimized currently

52 # 3. If the input kerning is already in several subtables, the subtables

53 # are not grouped together first; instead each subtable is treated

54 # independently, so currently this step is:

55 # Split existing subtables into more smaller subtables

56 gpos = font["GPOS"]

57 for lookup in gpos.table.LookupList.Lookup:

58 if lookup.LookupType == 2:

59 compact_lookup(font, level, lookup)

60 elif lookup.LookupType == 9 and lookup.SubTable[0].ExtensionLookupType == 2:

61 compact_ext_lookup(font, level, lookup)

62 return font

65def compact_lookup(font: TTFont, level: int, lookup: otTables.Lookup) -> None:

66 new_subtables = compact_pair_pos(font, level, lookup.SubTable)

67 lookup.SubTable = new_subtables

68 lookup.SubTableCount = len(new_subtables)

71def compact_ext_lookup(font: TTFont, level: int, lookup: otTables.Lookup) -> None:

72 new_subtables = compact_pair_pos(

73 font, level, [ext_subtable.ExtSubTable for ext_subtable in lookup.SubTable]

74 )

75 new_ext_subtables = []

76 for subtable in new_subtables:

77 ext_subtable = otTables.ExtensionPos()

78 ext_subtable.Format = 1

79 ext_subtable.ExtSubTable = subtable

80 new_ext_subtables.append(ext_subtable)

81 lookup.SubTable = new_ext_subtables

82 lookup.SubTableCount = len(new_ext_subtables)

85def compact_pair_pos(

86 font: TTFont, level: int, subtables: Sequence[otTables.PairPos]

87) -> Sequence[otTables.PairPos]:

88 new_subtables = []

89 for subtable in subtables:

90 if subtable.Format == 1:

91 # Not doing anything to Format 1 (yet?)

92 new_subtables.append(subtable)

93 elif subtable.Format == 2:

94 new_subtables.extend(compact_class_pairs(font, level, subtable))

95 return new_subtables

98def compact_class_pairs(

99 font: TTFont, level: int, subtable: otTables.PairPos

100) -> List[otTables.PairPos]:

101 from fontTools.otlLib.builder import buildPairPosClassesSubtable

102

103 subtables = []

104 classes1: DefaultDict[int, List[str]] = defaultdict(list)

105 for g in subtable.Coverage.glyphs:

106 classes1[subtable.ClassDef1.classDefs.get(g, 0)].append(g)

107 classes2: DefaultDict[int, List[str]] = defaultdict(list)

108 for g, i in subtable.ClassDef2.classDefs.items():

109 classes2[i].append(g)

110 all_pairs = {}

111 for i, class1 in enumerate(subtable.Class1Record):

112 for j, class2 in enumerate(class1.Class2Record):

113 if is_really_zero(class2):

114 continue

115 all_pairs[(tuple(sorted(classes1[i])), tuple(sorted(classes2[j])))] = (

116 getattr(class2, "Value1", None),

117 getattr(class2, "Value2", None),

118 )

119 grouped_pairs = cluster_pairs_by_class2_coverage_custom_cost(font, all_pairs, level)

120 for pairs in grouped_pairs:

121 subtables.append(buildPairPosClassesSubtable(pairs, font.getReverseGlyphMap()))

122 return subtables

123

124

125def is_really_zero(class2: otTables.Class2Record) -> bool:

126 v1 = getattr(class2, "Value1", None)

127 v2 = getattr(class2, "Value2", None)

128 return (v1 is None or v1.getEffectiveFormat() == 0) and (

129 v2 is None or v2.getEffectiveFormat() == 0

130 )

131

132

133Pairs = Dict[

134 Tuple[Tuple[str, ...], Tuple[str, ...]],

135 Tuple[otBase.ValueRecord, otBase.ValueRecord],

136]

137

138

139# Adapted from https://github.com/fonttools/fonttools/blob/f64f0b42f2d1163b2d85194e0979def539f5dca3/Lib/fontTools/ttLib/tables/otTables.py#L935-L958

140def _getClassRanges(glyphIDs: Iterable[int]):

141 glyphIDs = sorted(glyphIDs)

142 last = glyphIDs[0]

143 ranges = [[last]]

144 for glyphID in glyphIDs[1:]:

145 if glyphID != last + 1:

146 ranges[-1].append(last)

147 ranges.append([glyphID])

148 last = glyphID

149 ranges[-1].append(last)

150 return ranges, glyphIDs[0], glyphIDs[-1]

151

152

153# Adapted from https://github.com/fonttools/fonttools/blob/f64f0b42f2d1163b2d85194e0979def539f5dca3/Lib/fontTools/ttLib/tables/otTables.py#L960-L989

154def _classDef_bytes(

155 class_data: List[Tuple[List[Tuple[int, int]], int, int]],

156 class_ids: List[int],

157 coverage=False,

158):

159 if not class_ids:

160 return 0

161 first_ranges, min_glyph_id, max_glyph_id = class_data[class_ids[0]]

162 range_count = len(first_ranges)

163 for i in class_ids[1:]:

164 data = class_data[i]

165 range_count += len(data[0])

166 min_glyph_id = min(min_glyph_id, data[1])

167 max_glyph_id = max(max_glyph_id, data[2])

168 glyphCount = max_glyph_id - min_glyph_id + 1

169 # https://docs.microsoft.com/en-us/typography/opentype/spec/chapter2#class-definition-table-format-1

170 format1_bytes = 6 + glyphCount * 2

171 # https://docs.microsoft.com/en-us/typography/opentype/spec/chapter2#class-definition-table-format-2

172 format2_bytes = 4 + range_count * 6

173 return min(format1_bytes, format2_bytes)

174

175

176ClusteringContext = namedtuple(

177 "ClusteringContext",

178 [

179 "lines",

180 "all_class1",

181 "all_class1_data",

182 "all_class2_data",

183 "valueFormat1_bytes",

184 "valueFormat2_bytes",

185 ],

186)

187

188

189class Cluster:

190 # TODO(Python 3.7): Turn this into a dataclass

191 # ctx: ClusteringContext

192 # indices: int

193 # Caches

194 # TODO(Python 3.8): use functools.cached_property instead of the

195 # manually cached properties, and remove the cache fields listed below.

196 # _indices: Optional[List[int]] = None

197 # _column_indices: Optional[List[int]] = None

198 # _cost: Optional[int] = None

199

200 __slots__ = "ctx", "indices_bitmask", "_indices", "_column_indices", "_cost"

201

202 def __init__(self, ctx: ClusteringContext, indices_bitmask: int):

203 self.ctx = ctx

204 self.indices_bitmask = indices_bitmask

205 self._indices = None

206 self._column_indices = None

207 self._cost = None

208

209 @property

210 def indices(self):

211 if self._indices is None:

212 self._indices = bit_indices(self.indices_bitmask)

213 return self._indices

214

215 @property

216 def column_indices(self):

217 if self._column_indices is None:

218 # Indices of columns that have a 1 in at least 1 line

219 # => binary OR all the lines

220 bitmask = reduce(int.__or__, (self.ctx.lines[i] for i in self.indices))

221 self._column_indices = bit_indices(bitmask)

222 return self._column_indices

223

224 @property

225 def width(self):

226 # Add 1 because Class2=0 cannot be used but needs to be encoded.

227 return len(self.column_indices) + 1

228

229 @property

230 def cost(self):

231 if self._cost is None:

232 self._cost = (

233 # 2 bytes to store the offset to this subtable in the Lookup table above

234 2

235 # Contents of the subtable

236 # From: https://docs.microsoft.com/en-us/typography/opentype/spec/gpos#pair-adjustment-positioning-format-2-class-pair-adjustment

237 # uint16 posFormat Format identifier: format = 2

238 + 2

239 # Offset16 coverageOffset Offset to Coverage table, from beginning of PairPos subtable.

240 + 2

241 + self.coverage_bytes

242 # uint16 valueFormat1 ValueRecord definition — for the first glyph of the pair (may be zero).

243 + 2

244 # uint16 valueFormat2 ValueRecord definition — for the second glyph of the pair (may be zero).

245 + 2

246 # Offset16 classDef1Offset Offset to ClassDef table, from beginning of PairPos subtable — for the first glyph of the pair.

247 + 2

248 + self.classDef1_bytes

249 # Offset16 classDef2Offset Offset to ClassDef table, from beginning of PairPos subtable — for the second glyph of the pair.

250 + 2

251 + self.classDef2_bytes

252 # uint16 class1Count Number of classes in classDef1 table — includes Class 0.

253 + 2

254 # uint16 class2Count Number of classes in classDef2 table — includes Class 0.

255 + 2

256 # Class1Record class1Records[class1Count] Array of Class1 records, ordered by classes in classDef1.

257 + (self.ctx.valueFormat1_bytes + self.ctx.valueFormat2_bytes)

258 * len(self.indices)

259 * self.width

260 )

261 return self._cost

262

263 @property

264 def coverage_bytes(self):

265 format1_bytes = (

266 # From https://docs.microsoft.com/en-us/typography/opentype/spec/chapter2#coverage-format-1

267 # uint16 coverageFormat Format identifier — format = 1

268 # uint16 glyphCount Number of glyphs in the glyph array

269 4

270 # uint16 glyphArray[glyphCount] Array of glyph IDs — in numerical order

271 + sum(len(self.ctx.all_class1[i]) for i in self.indices) * 2

272 )

273 ranges = sorted(

274 chain.from_iterable(self.ctx.all_class1_data[i][0] for i in self.indices)

275 )

276 merged_range_count = 0

277 last = None

278 for start, end in ranges:

279 if last is not None and start != last + 1:

280 merged_range_count += 1

281 last = end

282 format2_bytes = (

283 # From https://docs.microsoft.com/en-us/typography/opentype/spec/chapter2#coverage-format-2

284 # uint16 coverageFormat Format identifier — format = 2

285 # uint16 rangeCount Number of RangeRecords

286 4

287 # RangeRecord rangeRecords[rangeCount] Array of glyph ranges — ordered by startGlyphID.

288 # uint16 startGlyphID First glyph ID in the range

289 # uint16 endGlyphID Last glyph ID in the range

290 # uint16 startCoverageIndex Coverage Index of first glyph ID in range

291 + merged_range_count * 6

292 )

293 return min(format1_bytes, format2_bytes)

294

295 @property

296 def classDef1_bytes(self):

297 # We can skip encoding one of the Class1 definitions, and use

298 # Class1=0 to represent it instead, because Class1 is gated by the

299 # Coverage definition. Use Class1=0 for the highest byte savings.

300 # Going through all options takes too long, pick the biggest class

301 # = what happens in otlLib.builder.ClassDefBuilder.classes()

302 biggest_index = max(self.indices, key=lambda i: len(self.ctx.all_class1[i]))

303 return _classDef_bytes(

304 self.ctx.all_class1_data, [i for i in self.indices if i != biggest_index]

305 )

306

307 @property

308 def classDef2_bytes(self):

309 # All Class2 need to be encoded because we can't use Class2=0

310 return _classDef_bytes(self.ctx.all_class2_data, self.column_indices)

311

312

313def cluster_pairs_by_class2_coverage_custom_cost(

314 font: TTFont,

315 pairs: Pairs,

316 compression: int = 5,

317) -> List[Pairs]:

318 if not pairs:

319 # The subtable was actually empty?

320 return [pairs]

321

322 # Sorted for reproducibility/determinism

323 all_class1 = sorted(set(pair[0] for pair in pairs))

324 all_class2 = sorted(set(pair[1] for pair in pairs))

325

326 # Use Python's big ints for binary vectors representing each line

327 lines = [

328 sum(

329 1 << i if (class1, class2) in pairs else 0

330 for i, class2 in enumerate(all_class2)

331 )

332 for class1 in all_class1

333 ]

334

335 # Map glyph names to ids and work with ints throughout for ClassDef formats

336 name_to_id = font.getReverseGlyphMap()

337 # Each entry in the arrays below is (range_count, min_glyph_id, max_glyph_id)

338 all_class1_data = [

339 _getClassRanges(name_to_id[name] for name in cls) for cls in all_class1

340 ]

341 all_class2_data = [

342 _getClassRanges(name_to_id[name] for name in cls) for cls in all_class2

343 ]

344

345 format1 = 0

346 format2 = 0

347 for pair, value in pairs.items():

348 format1 |= value[0].getEffectiveFormat() if value[0] else 0

349 format2 |= value[1].getEffectiveFormat() if value[1] else 0

350 valueFormat1_bytes = bit_count(format1) * 2

351 valueFormat2_bytes = bit_count(format2) * 2

352

353 ctx = ClusteringContext(

354 lines,

355 all_class1,

356 all_class1_data,

357 all_class2_data,

358 valueFormat1_bytes,

359 valueFormat2_bytes,

360 )

361

362 cluster_cache: Dict[int, Cluster] = {}

363

364 def make_cluster(indices: int) -> Cluster:

365 cluster = cluster_cache.get(indices, None)

366 if cluster is not None:

367 return cluster

368 cluster = Cluster(ctx, indices)

369 cluster_cache[indices] = cluster

370 return cluster

371

372 def merge(cluster: Cluster, other: Cluster) -> Cluster:

373 return make_cluster(cluster.indices_bitmask | other.indices_bitmask)

374

375 # Agglomerative clustering by hand, checking the cost gain of the new

376 # cluster against the previously separate clusters

377 # Start with 1 cluster per line

378 # cluster = set of lines = new subtable

379 clusters = [make_cluster(1 << i) for i in range(len(lines))]

380

381 # Cost of 1 cluster with everything

382 # `(1 << len) - 1` gives a bitmask full of 1's of length `len`

383 cost_before_splitting = make_cluster((1 << len(lines)) - 1).cost

384 log.debug(f" len(clusters) = {len(clusters)}")

385

386 while len(clusters) > 1:

387 lowest_cost_change = None

388 best_cluster_index = None

389 best_other_index = None

390 best_merged = None

391 for i, cluster in enumerate(clusters):

392 for j, other in enumerate(clusters[i + 1 :]):

393 merged = merge(cluster, other)

394 cost_change = merged.cost - cluster.cost - other.cost

395 if lowest_cost_change is None or cost_change < lowest_cost_change:

396 lowest_cost_change = cost_change

397 best_cluster_index = i

398 best_other_index = i + 1 + j

399 best_merged = merged

400 assert lowest_cost_change is not None

401 assert best_cluster_index is not None

402 assert best_other_index is not None

403 assert best_merged is not None

404

405 # If the best merge we found is still taking down the file size, then

406 # there's no question: we must do it, because it's beneficial in both

407 # ways (lower file size and lower number of subtables). However, if the

408 # best merge we found is not reducing file size anymore, then we need to

409 # look at the other stop criteria = the compression factor.

410 if lowest_cost_change > 0:

411 # Stop critera: check whether we should keep merging.

412 # Compute size reduction brought by splitting

413 cost_after_splitting = sum(c.cost for c in clusters)

414 # size_reduction so that after = before * (1 - size_reduction)

415 # E.g. before = 1000, after = 800, 1 - 800/1000 = 0.2

416 size_reduction = 1 - cost_after_splitting / cost_before_splitting

417

418 # Force more merging by taking into account the compression number.

419 # Target behaviour: compression number = 1 to 9, default 5 like gzip

420 # - 1 = accept to add 1 subtable to reduce size by 50%

421 # - 5 = accept to add 5 subtables to reduce size by 50%

422 # See https://github.com/harfbuzz/packtab/blob/master/Lib/packTab/__init__.py#L690-L691

423 # Given the size reduction we have achieved so far, compute how many

424 # new subtables are acceptable.

425 max_new_subtables = -log2(1 - size_reduction) * compression

426 log.debug(

427 f" len(clusters) = {len(clusters):3d} size_reduction={size_reduction:5.2f} max_new_subtables={max_new_subtables}",

428 )

429 if compression == 9:

430 # Override level 9 to mean: create any number of subtables

431 max_new_subtables = len(clusters)

432

433 # If we have managed to take the number of new subtables below the

434 # threshold, then we can stop.

435 if len(clusters) <= max_new_subtables + 1:

436 break

437

438 # No reason to stop yet, do the merge and move on to the next.

439 del clusters[best_other_index]

440 clusters[best_cluster_index] = best_merged

441

442 # All clusters are final; turn bitmasks back into the "Pairs" format

443 pairs_by_class1: Dict[Tuple[str, ...], Pairs] = defaultdict(dict)

444 for pair, values in pairs.items():

445 pairs_by_class1[pair[0]][pair] = values

446 pairs_groups: List[Pairs] = []

447 for cluster in clusters:

448 pairs_group: Pairs = dict()

449 for i in cluster.indices:

450 class1 = all_class1[i]

451 pairs_group.update(pairs_by_class1[class1])

452 pairs_groups.append(pairs_group)

453 return pairs_groups