write_fonts/tables/variations/
mivs_builder.rs

1//! Building the MultiItemVariationStore for VARC
2//!
3//! See also [`VariationStoreBuilder`]. Where Item Variation Stores stores a
4//! single scalar delta per region, [`MultiItemVariationStore`] stores a tuple
5//! of deltas per region, and uses a sparse representation of regions
6//! (only active axes are stored).
7//!
8//! [`VariationStoreBuilder`]: crate::tables::variations::ivs_builder::VariationStoreBuilder
9
10use std::collections::HashMap;
11
12use indexmap::IndexMap;
13use types::F2Dot14;
14
15use crate::{
16    error::Error,
17    tables::{
18        postscript::Index2,
19        varc::{
20            MultiItemVariationData, MultiItemVariationStore, SparseRegionAxisCoordinates,
21            SparseVariationRegion, SparseVariationRegionList,
22        },
23        variations::{
24            common_builder::{TemporaryDeltaSetId, VarStoreRemapping, NO_VARIATION_INDEX},
25            PackedDeltas,
26        },
27    },
28};
29
30pub type MultiVariationIndexRemapping = VarStoreRemapping<u32>;
31
32/// A sparse region definition, containing only axes with non-zero peaks.
33///
34/// This is used as a key for deduplicating regions in the builder.
35/// Each entry is (axis_index, start, peak, end).
36#[derive(Clone, Debug, Hash, PartialEq, Eq)]
37pub struct SparseRegion(Vec<(u16, F2Dot14, F2Dot14, F2Dot14)>);
38
39impl SparseRegion {
40    /// Create a new sparse region from axis coordinates.
41    ///
42    /// The coordinates should be in the form (axis_index, start, peak, end).
43    /// The region will be sorted by axis index for consistent hashing.
44    pub fn new(mut axes: Vec<(u16, F2Dot14, F2Dot14, F2Dot14)>) -> Self {
45        // Sort by axis index for consistent hashing/equality
46        axes.sort_by_key(|(idx, _, _, _)| *idx);
47        // Filter out axes with zero peak (they don't contribute)
48        axes.retain(|(_, _, peak, _)| peak.to_f32() != 0.0);
49        Self(axes)
50    }
51
52    /// Returns true if this region has no active axes.
53    pub fn is_empty(&self) -> bool {
54        self.0.is_empty()
55    }
56
57    fn to_sparse_variation_region(&self) -> SparseVariationRegion {
58        let region_axis_offsets = self
59            .0
60            .iter()
61            .map(|(axis_index, start, peak, end)| {
62                SparseRegionAxisCoordinates::new(*axis_index, *start, *peak, *end)
63            })
64            .collect::<Vec<_>>();
65        SparseVariationRegion::new(region_axis_offsets.len() as u16, region_axis_offsets)
66    }
67}
68
69/// A delta set for MIVS: tuples of deltas for each region.
70///
71/// Unlike IVS where each region has a single scalar delta, MIVS has a tuple
72/// of N values per region (e.g., for x,y coordinates or transform values).
73#[derive(Clone, Debug, Hash, PartialEq, Eq)]
74struct MultiDeltaSet {
75    /// The tuple length (number of values per region).
76    tuple_len: usize,
77    /// Per-region delta tuples, stored as (region_index, [delta0, delta1, ...]).
78    /// Sorted by region index.
79    deltas: Vec<(u16, Vec<i32>)>,
80}
81
82impl MultiDeltaSet {
83    fn new(tuple_len: usize, mut deltas: Vec<(u16, Vec<i32>)>) -> Result<Self, Error> {
84        // Sort by region index
85        deltas.sort_by_key(|(idx, _)| *idx);
86        // Verify all tuples have the expected length
87        if !deltas.iter().all(|(_, tuple)| tuple.len() == tuple_len) {
88            return Err(Error::InvalidInput(
89                "all delta tuples in MultiDeltaSet must have the same length",
90            ));
91        };
92        // Filter out all-zero tuples
93        deltas.retain(|(_, tuple)| tuple.iter().any(|v| *v != 0));
94        Ok(Self { tuple_len, deltas })
95    }
96
97    fn is_empty(&self) -> bool {
98        self.deltas.is_empty()
99    }
100}
101
102/// A builder for the [`MultiItemVariationStore`]
103///
104/// This handles assigning VariationIndex values to unique sets of tuple deltas
105/// and grouping delta sets into [`MultiItemVariationData`] subtables.
106#[derive(Clone, Debug, Default)]
107pub struct MultiItemVariationStoreBuilder {
108    /// Maps SparseRegion to its index in the region list.
109    all_regions: HashMap<SparseRegion, usize>,
110    /// Deduplicates identical delta sets.
111    /// Maps delta set -> temporary ID.
112    delta_sets: IndexMap<MultiDeltaSet, TemporaryDeltaSetId>,
113    /// Counter for generating temporary IDs.
114    next_id: TemporaryDeltaSetId,
115}
116
117impl MultiItemVariationStoreBuilder {
118    /// Create a new builder.
119    pub fn new() -> Self {
120        Self::default()
121    }
122
123    /// Returns `true` if no deltas have been added to this builder.
124    pub fn is_empty(&self) -> bool {
125        self.delta_sets.is_empty()
126    }
127
128    /// Add a set of tuple deltas and return a temporary ID.
129    ///
130    /// # Arguments
131    ///
132    /// * `deltas` - Vec of (SparseRegion, delta_tuple) pairs.
133    ///   Each delta_tuple must have the same length.
134    ///
135    /// # Returns
136    ///
137    /// A temporary ID that can be used to retrieve the final VarIdx after
138    /// calling [`build`](Self::build).
139    ///
140    /// Returns an error if the delta tuples have inconsistent lengths.
141    pub fn add_deltas<T: Into<i32>>(
142        &mut self,
143        deltas: Vec<(SparseRegion, Vec<T>)>,
144    ) -> Result<TemporaryDeltaSetId, Error> {
145        // Determine tuple length from first non-empty entry
146        let tuple_len = deltas
147            .iter()
148            .map(|(_, tuple)| tuple.len())
149            .next()
150            .unwrap_or(0);
151
152        // Convert regions to indices and collect delta tuples
153        let mut indexed_deltas = Vec::with_capacity(deltas.len());
154        for (region, tuple) in deltas {
155            assert_eq!(
156                tuple.len(),
157                tuple_len,
158                "all delta tuples must have the same length"
159            );
160            if region.is_empty() {
161                continue;
162            }
163            let region_idx = self.canonical_index_for_region(region) as u16;
164            let converted_tuple: Vec<i32> = tuple.into_iter().map(|v| v.into()).collect();
165            indexed_deltas.push((region_idx, converted_tuple));
166        }
167
168        let delta_set = MultiDeltaSet::new(tuple_len, indexed_deltas)?;
169
170        // Return NO_VARIATION_INDEX for empty delta sets
171        if delta_set.is_empty() {
172            return Ok(NO_VARIATION_INDEX);
173        }
174
175        // Deduplicate
176        if let Some(&existing_id) = self.delta_sets.get(&delta_set) {
177            return Ok(existing_id);
178        }
179
180        let id = self.next_id;
181        self.next_id += 1;
182        self.delta_sets.insert(delta_set, id);
183        Ok(id)
184    }
185
186    fn canonical_index_for_region(&mut self, region: SparseRegion) -> usize {
187        let next_idx = self.all_regions.len();
188        *self.all_regions.entry(region).or_insert(next_idx)
189    }
190
191    /// Build the [`MultiItemVariationStore`] table.
192    ///
193    /// This also returns a structure that can be used to remap the temporarily
194    /// assigned delta set IDs to their final `VarIdx` values.
195    pub fn build(self) -> (MultiItemVariationStore, MultiVariationIndexRemapping) {
196        if self.delta_sets.is_empty() {
197            // Return an empty store
198            let region_list = SparseVariationRegionList::new(0, vec![]);
199            let store = MultiItemVariationStore::new(region_list, 0, vec![]);
200            return (store, MultiVariationIndexRemapping::default());
201        }
202
203        // Group delta sets by their region indices (like Python's _varDataIndices)
204        let mut var_data_groups: IndexMap<Vec<u16>, Vec<(&MultiDeltaSet, TemporaryDeltaSetId)>> =
205            IndexMap::new();
206
207        for (delta_set, temp_id) in &self.delta_sets {
208            let region_indices: Vec<u16> = delta_set.deltas.iter().map(|(idx, _)| *idx).collect();
209            var_data_groups
210                .entry(region_indices)
211                .or_default()
212                .push((delta_set, *temp_id));
213        }
214
215        // Build region list
216        let region_list = self.build_region_list();
217
218        // Build MultiVarData subtables
219        let mut key_map = MultiVariationIndexRemapping::default();
220        let mut var_data_tables = Vec::new();
221
222        for (outer, (region_indices, delta_sets)) in var_data_groups.into_iter().enumerate() {
223            // Split into chunks of 0xFFFF if needed
224            for chunk in delta_sets.chunks(0xFFFF) {
225                let subtable =
226                    self.build_var_data(&region_indices, chunk, outer as u16, &mut key_map);
227                var_data_tables.push(subtable);
228            }
229        }
230
231        let store = MultiItemVariationStore::new(
232            region_list,
233            var_data_tables.len() as u16,
234            var_data_tables,
235        );
236
237        (store, key_map)
238    }
239
240    fn build_region_list(&self) -> SparseVariationRegionList {
241        // Sort regions by their canonical index
242        let mut regions: Vec<_> = self.all_regions.iter().collect();
243        regions.sort_by_key(|(_, idx)| *idx);
244
245        let sparse_regions: Vec<SparseVariationRegion> = regions
246            .into_iter()
247            .map(|(region, _)| region.to_sparse_variation_region())
248            .collect();
249
250        SparseVariationRegionList::new(sparse_regions.len() as u16, sparse_regions)
251    }
252
253    fn build_var_data(
254        &self,
255        region_indices: &[u16],
256        delta_sets: &[(&MultiDeltaSet, TemporaryDeltaSetId)],
257        outer: u16,
258        key_map: &mut MultiVariationIndexRemapping,
259    ) -> MultiItemVariationData {
260        // Build the CFF2 Index containing packed delta sets
261        let mut items = Vec::new();
262
263        for (inner, (delta_set, temp_id)) in delta_sets.iter().enumerate() {
264            // Flatten the delta tuples in region order
265            let flattened = self.flatten_deltas(delta_set, region_indices);
266
267            // Encode as PackedDeltas (TupleValues)
268            let packed = PackedDeltas::new(flattened);
269            let mut encoded = Vec::new();
270            // We need to manually encode since PackedDeltas uses TableWriter
271            encode_packed_deltas(&packed, &mut encoded);
272
273            items.push(encoded);
274
275            // Record the mapping
276            let var_idx = ((outer as u32) << 16) | (inner as u32);
277            key_map.set(*temp_id, var_idx);
278        }
279
280        let index2 = Index2::from_items(items);
281        let raw_delta_sets = crate::dump_table(&index2).expect("Index2 serialization failed");
282
283        MultiItemVariationData::new(
284            region_indices.len() as u16,
285            region_indices.to_vec(),
286            raw_delta_sets,
287        )
288    }
289
290    /// Flatten delta tuples into a single vector in region order.
291    ///
292    /// For each region in `region_indices`, we output the corresponding tuple's
293    /// values (or zeros if no delta exists for that region).
294    fn flatten_deltas(&self, delta_set: &MultiDeltaSet, region_indices: &[u16]) -> Vec<i32> {
295        let tuple_len = delta_set.tuple_len;
296        let mut result = Vec::with_capacity(region_indices.len() * tuple_len);
297
298        // Build a map from region index to delta tuple
299        let delta_map: HashMap<u16, &Vec<i32>> = delta_set
300            .deltas
301            .iter()
302            .map(|(idx, tuple)| (*idx, tuple))
303            .collect();
304
305        for &region_idx in region_indices {
306            if let Some(tuple) = delta_map.get(&region_idx) {
307                result.extend(tuple.iter().copied());
308            } else {
309                // No delta for this region - output zeros
310                result.extend(std::iter::repeat_n(0, tuple_len));
311            }
312        }
313
314        result
315    }
316}
317
318/// Encode PackedDeltas to bytes.
319///
320/// This is a helper since PackedDeltas normally writes via TableWriter.
321fn encode_packed_deltas(packed: &PackedDeltas, output: &mut Vec<u8>) {
322    use crate::write::FontWrite;
323
324    // Use a TableWriter to get the bytes
325    let mut writer = crate::write::TableWriter::default();
326    packed.write_into(&mut writer);
327
328    // Extract the bytes from the writer's internal data
329    let data = writer.into_data();
330    output.extend(&data.bytes);
331}
332
333#[cfg(test)]
334mod tests {
335    use super::*;
336
337    fn f2dot14(val: f32) -> F2Dot14 {
338        F2Dot14::from_f32(val)
339    }
340
341    #[test]
342    fn empty_builder() {
343        let builder = MultiItemVariationStoreBuilder::new();
344        assert!(builder.is_empty());
345
346        let (store, _remap) = builder.build();
347        assert_eq!(store.variation_data_count, 0);
348    }
349
350    #[test]
351    fn single_delta_set() {
352        let mut builder = MultiItemVariationStoreBuilder::new();
353
354        let region = SparseRegion::new(vec![(0, f2dot14(0.0), f2dot14(1.0), f2dot14(1.0))]);
355
356        // Add a 2-tuple delta
357        let temp_id = builder.add_deltas(vec![(region, vec![10, 20])]).unwrap();
358
359        assert!(temp_id != NO_VARIATION_INDEX);
360        assert!(!builder.is_empty());
361
362        let (store, remap) = builder.build();
363
364        // Should have 1 region
365        assert_eq!(store.region_list.region_count, 1);
366
367        // Should have 1 var data subtable
368        assert_eq!(store.variation_data_count, 1);
369
370        // The temp_id should map to (0, 0)
371        let var_idx = remap.get(temp_id).unwrap();
372        assert_eq!(var_idx >> 16, 0); // outer = 0
373        assert_eq!(var_idx & 0xFFFF, 0); // inner = 0
374    }
375
376    #[test]
377    fn deduplication() {
378        let mut builder = MultiItemVariationStoreBuilder::new();
379
380        let region = SparseRegion::new(vec![(0, f2dot14(0.0), f2dot14(1.0), f2dot14(1.0))]);
381
382        // Add the same delta set twice
383        let id1 = builder
384            .add_deltas(vec![(region.clone(), vec![10, 20])])
385            .unwrap();
386        let id2 = builder.add_deltas(vec![(region, vec![10, 20])]).unwrap();
387
388        // Should get the same ID
389        assert_eq!(id1, id2);
390    }
391
392    #[test]
393    fn empty_delta_returns_no_variation_index() {
394        let mut builder = MultiItemVariationStoreBuilder::new();
395
396        // Empty deltas
397        let id = builder.add_deltas::<i32>(vec![]).unwrap();
398        assert_eq!(id, NO_VARIATION_INDEX);
399
400        // All-zero deltas
401        let region = SparseRegion::new(vec![(0, f2dot14(0.0), f2dot14(1.0), f2dot14(1.0))]);
402        let id = builder.add_deltas(vec![(region, vec![0, 0])]).unwrap();
403        assert_eq!(id, NO_VARIATION_INDEX);
404    }
405
406    #[test]
407    fn multiple_regions() {
408        let mut builder = MultiItemVariationStoreBuilder::new();
409
410        let region1 = SparseRegion::new(vec![(0, f2dot14(0.0), f2dot14(1.0), f2dot14(1.0))]);
411        let region2 = SparseRegion::new(vec![(1, f2dot14(0.0), f2dot14(1.0), f2dot14(1.0))]);
412
413        let temp_id = builder
414            .add_deltas(vec![(region1, vec![10, 20]), (region2, vec![30, 40])])
415            .unwrap();
416
417        assert!(temp_id != NO_VARIATION_INDEX);
418
419        let (store, _remap) = builder.build();
420
421        // Should have 2 regions
422        assert_eq!(store.region_list.region_count, 2);
423    }
424}
write_fonts/tables/variations/mivs_builder.rs

write_fonts/tables/variations/
mivs_builder.rs
