Skip to main content

harfrust/ot/
map.rs

1use alloc::boxed::Box;
2use alloc::vec::Vec;
3use core::cmp::Ordering;
4use core::ops::Range;
5
6use super::buffer::{Buffer, GlyphFlags};
7use super::layout::LayoutTableKind;
8use super::{Language, Mask, Script, Tag};
9use crate::plan::ShapePlan;
10use crate::tag::TagExt;
11use crate::{LayoutData, ShaperFont};
12use read_fonts::tables::layout::{store_deltas, LookupVariations};
13use read_fonts::types::F2Dot14;
14
15// TODO: Remove once MSRV is 1.80+
16use core::mem::{size_of, size_of_val};
17
18pub struct OtMap {
19    found_script: [bool; 2],
20    chosen_script: [Option<Tag>; 2],
21    global_mask: Mask,
22    features: Vec<FeatureMap>,
23    lookups: [Vec<LookupMap>; 2],
24    stages: [Vec<StageMap>; 2],
25    feature_variations: [Option<u32>; 2],
26    /// The location lookup variations were resolved at, if the font has any.
27    lookup_coords: Option<Box<[F2Dot14]>>,
28}
29
30#[derive(Clone, Copy, Debug, PartialEq, Eq)]
31pub struct FeatureMap {
32    tag: Tag,
33    // GSUB/GPOS
34    index: [Option<u16>; 2],
35    stage: [usize; 2],
36    shift: u32,
37    mask: Mask,
38    // mask for value=1, for quick access
39    one_mask: Mask,
40    needs_fallback: bool,
41    auto_zwnj: bool,
42    auto_zwj: bool,
43    random: bool,
44    per_syllable: bool,
45}
46
47impl Ord for FeatureMap {
48    fn cmp(&self, other: &Self) -> Ordering {
49        self.tag.cmp(&other.tag)
50    }
51}
52
53impl PartialOrd for FeatureMap {
54    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {
55        self.tag.partial_cmp(&other.tag)
56    }
57}
58
59#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
60pub struct LookupMap {
61    pub index: u16,
62    // TODO: to bitflags
63    pub auto_zwnj: bool,
64    pub auto_zwj: bool,
65    pub random: bool,
66    pub mask: Mask,
67    pub per_syllable: bool,
68    #[cfg(feature = "tracing")]
69    pub feature_tag: Tag,
70}
71
72// HarfBuzz prints tag bytes directly, whereas Tag's Display escapes them.
73#[cfg(feature = "tracing")]
74pub(crate) struct MessageTag(pub Option<Tag>);
75
76#[cfg(feature = "tracing")]
77impl core::fmt::Display for MessageTag {
78    fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result {
79        use core::fmt::Write;
80        if let Some(tag) = self.0 {
81            for &byte in tag.as_ref() {
82                // Script tags use a C string; feature tags use four %c fields.
83                if f.alternate() && byte == 0 {
84                    break;
85                }
86                f.write_char(char::from(byte))?;
87            }
88        }
89        Ok(())
90    }
91}
92
93#[derive(Clone, Copy)]
94pub struct StageMap {
95    // Cumulative
96    pub last_lookup: usize,
97    pub pause_func: Option<PauseFn>,
98}
99
100// Pause functions return true if new glyph indices might have been added to the buffer.
101// This is used to update buffer digest.
102pub type PauseFn = fn(&ShapePlan, &ShaperFont<'_, '_>, &mut Buffer) -> Option<bool>;
103
104impl OtMap {
105    pub const MAX_BITS: u32 = 8;
106    pub const MAX_VALUE: u32 = (1 << Self::MAX_BITS) - 1;
107
108    #[inline]
109    pub fn found_script(&self, table_index: LayoutTableKind) -> bool {
110        self.found_script[table_index]
111    }
112
113    #[inline]
114    pub fn chosen_script(&self, table_index: LayoutTableKind) -> Option<Tag> {
115        self.chosen_script[table_index]
116    }
117
118    #[inline]
119    pub fn get_global_mask(&self) -> Mask {
120        self.global_mask
121    }
122
123    #[inline]
124    pub fn get_mask(&self, feature_tag: Tag) -> (Mask, u32) {
125        self.features
126            .binary_search_by_key(&feature_tag, |f| f.tag)
127            .map_or((0, 0), |idx| {
128                (self.features[idx].mask, self.features[idx].shift)
129            })
130    }
131
132    #[inline]
133    pub fn get_1_mask(&self, feature_tag: Tag) -> Mask {
134        self.features
135            .binary_search_by_key(&feature_tag, |f| f.tag)
136            .map_or(0, |idx| self.features[idx].one_mask)
137    }
138
139    #[inline]
140    pub fn needs_fallback(&self, feature_tag: Tag) -> bool {
141        self.features
142            .binary_search_by_key(&feature_tag, |f| f.tag)
143            .is_ok_and(|idx| self.features[idx].needs_fallback)
144    }
145
146    #[inline]
147    pub fn get_feature_index(&self, table_index: LayoutTableKind, feature_tag: Tag) -> Option<u16> {
148        self.features
149            .binary_search_by_key(&feature_tag, |f| f.tag)
150            .ok()
151            .and_then(|idx| self.features[idx].index[table_index])
152    }
153
154    #[inline]
155    pub fn get_feature_stage(
156        &self,
157        table_index: LayoutTableKind,
158        feature_tag: Tag,
159    ) -> Option<usize> {
160        self.features
161            .binary_search_by_key(&feature_tag, |f| f.tag)
162            .map(|idx| self.features[idx].stage[table_index])
163            .ok()
164    }
165
166    #[inline]
167    pub fn stages(&self, table_index: LayoutTableKind) -> &[StageMap] {
168        &self.stages[table_index]
169    }
170
171    #[inline]
172    pub fn lookup(&self, table_index: LayoutTableKind, index: usize) -> &LookupMap {
173        &self.lookups[table_index][index]
174    }
175
176    #[inline]
177    pub fn stage_lookups(&self, table_index: LayoutTableKind, stage: usize) -> &[LookupMap] {
178        &self.lookups[table_index][self.stage_lookup_range(table_index, stage)]
179    }
180
181    #[inline]
182    pub fn stage_lookup_range(&self, table_index: LayoutTableKind, stage: usize) -> Range<usize> {
183        let stages = &self.stages[table_index];
184        let lookups = &self.lookups[table_index];
185        let start = stage
186            .checked_sub(1)
187            .map_or(0, |prev| stages[prev].last_lookup);
188        let end = stages
189            .get(stage)
190            .map_or(lookups.len(), |curr| curr.last_lookup);
191        start..end
192    }
193
194    pub fn feature_variations(&self) -> &[Option<u32>; 2] {
195        &self.feature_variations
196    }
197
198    pub fn lookup_coords(&self) -> Option<&[F2Dot14]> {
199        self.lookup_coords.as_deref()
200    }
201}
202
203pub type MapFeatureFlags = u32;
204pub const F_NONE: u32 = 0x0000;
205pub const F_GLOBAL: u32 = 0x0001; /* Feature applies to all characters; results in no mask allocated for it. */
206pub const F_HAS_FALLBACK: u32 = 0x0002; /* Has fallback implementation, so include mask bit even if feature not found. */
207pub const F_MANUAL_ZWNJ: u32 = 0x0004; /* Don't skip over ZWNJ when matching **context**. */
208pub const F_MANUAL_ZWJ: u32 = 0x0008; /* Don't skip over ZWJ when matching **input**. */
209pub const F_MANUAL_JOINERS: u32 = F_MANUAL_ZWNJ | F_MANUAL_ZWJ;
210pub const F_GLOBAL_MANUAL_JOINERS: u32 = F_GLOBAL | F_MANUAL_JOINERS;
211pub const F_GLOBAL_HAS_FALLBACK: u32 = F_GLOBAL | F_HAS_FALLBACK;
212pub const F_GLOBAL_SEARCH: u32 = 0x0010; /* If feature not found in LangSys, look for it in global feature list and pick one. */
213pub const F_RANDOM: u32 = 0x0020; /* Randomly select a glyph from an AlternateSubstFormat1 subtable. */
214pub const F_PER_SYLLABLE: u32 = 0x0040; /* Contain lookup application to within syllable. */
215
216pub struct OtMapBuilder<'a> {
217    layout: LayoutData<'a>,
218    found_script: [bool; 2],
219    script_index: [Option<u16>; 2],
220    chosen_script: [Option<Tag>; 2],
221    lang_index: [Option<u16>; 2],
222    current_stage: [usize; 2],
223    feature_infos: Vec<FeatureInfo>,
224    stages: [Vec<StageInfo>; 2],
225    pub(crate) is_simple: bool,
226}
227
228#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord)]
229struct FeatureInfo {
230    tag: Tag,
231    // sequence number, used for stable sorting only
232    seq: usize,
233    max_value: u32,
234    flags: MapFeatureFlags,
235    // for non-global features, what should the unset glyphs take
236    default_value: u32,
237    // GSUB/GPOS
238    stage: [usize; 2],
239}
240
241#[derive(Clone, Copy)]
242struct StageInfo {
243    index: usize,
244    pause_func: Option<PauseFn>,
245}
246
247const GLOBAL_BIT_SHIFT: u32 = 8 * size_of::<u32>() as u32 - 1;
248const GLOBAL_BIT_MASK: Mask = 1 << GLOBAL_BIT_SHIFT;
249
250impl<'a> OtMapBuilder<'a> {
251    pub fn new(
252        layout: LayoutData<'a>,
253        script: Option<Script>,
254        language: Option<&Language>,
255    ) -> Self {
256        // Fetch script/language indices for GSUB/GPOS.  We need these later to skip
257        // features not available in either table and not waste precious bits for them.
258        let (script_tags, lang_tags) = Script::tags_for_language(script, language);
259
260        let mut found_script = [false; 2];
261        let mut script_index = [None; 2];
262        let mut chosen_script = [None; 2];
263        let mut lang_index = [None; 2];
264
265        for (table_index, table) in layout.ot.layout_tables() {
266            if let Some((found, idx, tag)) = table.select_script(script_tags.as_slice()) {
267                chosen_script[table_index] = Some(tag);
268                found_script[table_index] = found;
269                script_index[table_index] = Some(idx);
270
271                if let Some(idx) = table.select_script_language(idx, lang_tags.as_slice()) {
272                    lang_index[table_index] = Some(idx);
273                }
274            }
275        }
276
277        Self {
278            layout,
279            found_script,
280            script_index,
281            chosen_script,
282            lang_index,
283            current_stage: [0, 0],
284            feature_infos: Vec::new(),
285            stages: [Vec::new(), Vec::new()],
286            is_simple: false,
287        }
288    }
289
290    #[inline]
291    pub fn chosen_script(&self, table_index: LayoutTableKind) -> Option<Tag> {
292        self.chosen_script[table_index]
293    }
294
295    #[inline]
296    pub fn has_feature(&self, tag: Tag) -> bool {
297        for (table_index, table) in self.layout.ot.layout_tables() {
298            if let Some(script_index) = self.script_index[table_index] {
299                if table
300                    .find_language_feature(script_index, self.lang_index[table_index], tag)
301                    .is_some()
302                {
303                    return true;
304                }
305            }
306        }
307
308        false
309    }
310
311    #[inline]
312    pub fn add_feature(&mut self, tag: Tag, flags: MapFeatureFlags, value: u32) {
313        if !tag.is_null() {
314            let seq = self.feature_infos.len();
315            self.feature_infos.push(FeatureInfo {
316                tag,
317                seq,
318                max_value: value,
319                flags,
320                default_value: if flags & F_GLOBAL != 0 { value } else { 0 },
321                stage: self.current_stage,
322            });
323        }
324    }
325
326    #[inline]
327    pub fn enable_feature(&mut self, tag: Tag, flags: MapFeatureFlags, value: u32) {
328        self.add_feature(tag, flags | F_GLOBAL, value);
329    }
330
331    #[inline]
332    pub fn disable_feature(&mut self, tag: Tag) {
333        self.add_feature(tag, F_GLOBAL, 0);
334    }
335
336    #[inline]
337    pub fn add_gsub_pause(&mut self, pause: Option<PauseFn>) {
338        self.add_pause(LayoutTableKind::Gsub, pause);
339    }
340
341    #[inline]
342    pub fn add_gpos_pause(&mut self, pause: Option<PauseFn>) {
343        self.add_pause(LayoutTableKind::Gpos, pause);
344    }
345
346    fn add_pause(&mut self, table_index: LayoutTableKind, pause: Option<PauseFn>) {
347        self.stages[table_index].push(StageInfo {
348            index: self.current_stage[table_index],
349            pause_func: pause,
350        });
351
352        self.current_stage[table_index] += 1;
353    }
354
355    pub fn compile(&mut self) -> OtMap {
356        // We default to applying required feature in stage 0.  If the required
357        // feature has a tag that is known to the shaper, we apply required feature
358        // in the stage for that tag.
359        let mut required_index = [None; 2];
360        let mut required_tag = [None; 2];
361
362        for (table_index, table) in self.layout.ot.layout_tables() {
363            if let Some(script) = self.script_index[table_index] {
364                let lang = self.lang_index[table_index];
365                if let Some((idx, tag)) = table.get_required_language_feature(script, lang) {
366                    required_index[table_index] = Some(idx);
367                    required_tag[table_index] = Some(tag);
368                }
369            }
370        }
371
372        let (features, required_stage, global_mask) = self.collect_feature_maps(required_tag);
373
374        self.add_gsub_pause(None);
375        self.add_gpos_pause(None);
376
377        let (lookups, stages) =
378            self.collect_lookup_stages(&features, required_index, required_stage);
379
380        OtMap {
381            found_script: self.found_script,
382            chosen_script: self.chosen_script,
383            global_mask,
384            features,
385            lookups,
386            stages,
387            feature_variations: self.layout.ot.feature_variations,
388            lookup_coords: self
389                .layout
390                .ot
391                .has_lookup_variations
392                .then(|| self.layout.ot.coords.into()),
393        }
394    }
395
396    fn collect_feature_maps(
397        &mut self,
398        required_tag: [Option<Tag>; 2],
399    ) -> (Vec<FeatureMap>, [usize; 2], Mask) {
400        let mut map_features = Vec::new();
401        let mut required_stage = [0; 2];
402        let mut global_mask = GLOBAL_BIT_MASK;
403        let mut next_bit = GlyphFlags::DEFINED_BITS.count_ones() + 1;
404
405        // Sort features and merge duplicates.
406        self.dedup_feature_infos();
407
408        for info in &self.feature_infos {
409            let bits_needed = if info.flags & F_GLOBAL != 0 && info.max_value == 1 {
410                // Uses the global bit.
411                0
412            } else {
413                // Limit bits per feature.
414                let v = info.max_value;
415                let num_bits = 8 * size_of_val(&v) as u32 - v.leading_zeros();
416                OtMap::MAX_BITS.min(num_bits)
417            };
418
419            if info.max_value == 0 || next_bit + bits_needed >= GLOBAL_BIT_SHIFT {
420                // Feature disabled, or not enough bits.
421                continue;
422            }
423
424            let mut found = false;
425            let mut feature_index = [None; 2];
426
427            for (table_index, table) in self.layout.ot.layout_tables() {
428                if required_tag[table_index] == Some(info.tag) {
429                    required_stage[table_index] = info.stage[table_index];
430                }
431
432                if let Some(script) = self.script_index[table_index] {
433                    let lang = self.lang_index[table_index];
434                    if let Some(idx) = table.find_language_feature(script, lang, info.tag) {
435                        feature_index[table_index] = Some(idx);
436                        found = true;
437                    }
438                }
439            }
440
441            if !found && info.flags & F_GLOBAL_SEARCH != 0 {
442                // hb_ot_layout_table_find_feature
443                for (table_index, table) in self.layout.ot.layout_tables() {
444                    if let Some(idx) = table.feature_index(info.tag) {
445                        feature_index[table_index] = Some(idx);
446                        found = true;
447                    }
448                }
449            }
450
451            if !found && !info.flags & F_HAS_FALLBACK != 0 {
452                continue;
453            }
454
455            let (shift, mask) = if info.flags & F_GLOBAL != 0 && info.max_value == 1 {
456                // Uses the global bit
457                (GLOBAL_BIT_SHIFT, GLOBAL_BIT_MASK)
458            } else {
459                let shift = next_bit;
460                let mask = (1 << (next_bit + bits_needed)) - (1 << next_bit);
461                next_bit += bits_needed;
462                global_mask |= (info.default_value << shift) & mask;
463                (shift, mask)
464            };
465
466            map_features.push(FeatureMap {
467                tag: info.tag,
468                index: feature_index,
469                stage: info.stage,
470                shift,
471                mask,
472                one_mask: (1 << shift) & mask,
473                needs_fallback: !found,
474                auto_zwnj: info.flags & F_MANUAL_ZWNJ == 0,
475                auto_zwj: info.flags & F_MANUAL_ZWJ == 0,
476                random: info.flags & F_RANDOM != 0,
477                per_syllable: info.flags & F_PER_SYLLABLE != 0,
478            });
479        }
480
481        if self.is_simple {
482            crate::algs::sort_unstable_by(&mut map_features, Ord::cmp);
483        }
484
485        (map_features, required_stage, global_mask)
486    }
487
488    fn dedup_feature_infos(&mut self) {
489        let feature_infos = &mut self.feature_infos;
490        if feature_infos.is_empty() {
491            return;
492        }
493
494        if !self.is_simple {
495            crate::algs::sort_unstable_by(feature_infos, Ord::cmp);
496        }
497
498        let mut j = 0;
499        for i in 1..feature_infos.len() {
500            if feature_infos[i].tag != feature_infos[j].tag {
501                j += 1;
502                feature_infos[j] = feature_infos[i];
503            } else {
504                if feature_infos[i].flags & F_GLOBAL != 0 {
505                    feature_infos[j].flags |= F_GLOBAL;
506                    feature_infos[j].max_value = feature_infos[i].max_value;
507                    feature_infos[j].default_value = feature_infos[i].default_value;
508                } else {
509                    if feature_infos[j].flags & F_GLOBAL != 0 {
510                        feature_infos[j].flags ^= F_GLOBAL;
511                    }
512                    feature_infos[j].max_value =
513                        feature_infos[j].max_value.max(feature_infos[i].max_value);
514                    // Inherit default_value from j
515                }
516                let flags = feature_infos[i].flags & F_HAS_FALLBACK;
517                feature_infos[j].flags |= flags;
518                feature_infos[j].stage[0] =
519                    feature_infos[j].stage[0].min(feature_infos[i].stage[0]);
520                feature_infos[j].stage[1] =
521                    feature_infos[j].stage[1].min(feature_infos[i].stage[1]);
522            }
523        }
524
525        feature_infos.truncate(j + 1);
526    }
527
528    fn collect_lookup_stages(
529        &self,
530        map_features: &[FeatureMap],
531        required_feature_index: [Option<u16>; 2],
532        required_feature_stage: [usize; 2],
533    ) -> ([Vec<LookupMap>; 2], [Vec<StageMap>; 2]) {
534        let mut map_lookups = [Vec::new(), Vec::new()];
535        let mut map_stages = [Vec::new(), Vec::new()];
536
537        for table_index in LayoutTableKind::iter() {
538            // Collect lookup indices for features.
539            let mut stage_index = 0;
540            let mut last_lookup = 0;
541
542            let variation_index = self.layout.ot.feature_variations[table_index as usize];
543            let lookup_variations = if self.layout.ot.has_lookup_variations {
544                self.layout
545                    .ot
546                    .layout_table(table_index)
547                    .and_then(|table| table.lookup_variations())
548            } else {
549                None
550            };
551
552            for stage in 0..self.current_stage[table_index] {
553                if let Some(feature_index) = required_feature_index[table_index] {
554                    if required_feature_stage[table_index] == stage {
555                        self.add_lookups(
556                            &mut map_lookups[table_index],
557                            table_index,
558                            feature_index,
559                            variation_index,
560                            lookup_variations.as_ref(),
561                            GLOBAL_BIT_MASK,
562                            true,
563                            true,
564                            false,
565                            false,
566                            #[cfg(feature = "tracing")]
567                            Tag::new(b"    "),
568                        );
569                    }
570                }
571
572                for feature in map_features {
573                    if let Some(feature_index) = feature.index[table_index] {
574                        if feature.stage[table_index] == stage {
575                            self.add_lookups(
576                                &mut map_lookups[table_index],
577                                table_index,
578                                feature_index,
579                                variation_index,
580                                lookup_variations.as_ref(),
581                                feature.mask,
582                                feature.auto_zwnj,
583                                feature.auto_zwj,
584                                feature.random,
585                                feature.per_syllable,
586                                #[cfg(feature = "tracing")]
587                                feature.tag,
588                            );
589                        }
590                    }
591                }
592
593                // Sort lookups and merge duplicates.
594                let lookups = &mut map_lookups[table_index];
595                let len = lookups.len();
596
597                if last_lookup + 1 < len {
598                    crate::algs::sort_unstable_by(&mut lookups[last_lookup..], Ord::cmp);
599
600                    let mut j = last_lookup;
601                    for i in j + 1..len {
602                        if lookups[i].index != lookups[j].index {
603                            j += 1;
604                            lookups[j] = lookups[i];
605                        } else {
606                            lookups[j].mask |= lookups[i].mask;
607                            lookups[j].auto_zwnj &= lookups[i].auto_zwnj;
608                            lookups[j].auto_zwj &= lookups[i].auto_zwj;
609                        }
610                    }
611
612                    lookups.truncate(j + 1);
613                }
614
615                last_lookup = lookups.len();
616
617                if let Some(info) = self.stages[table_index].get(stage_index) {
618                    if info.index == stage {
619                        map_stages[table_index].push(StageMap {
620                            last_lookup,
621                            pause_func: info.pause_func,
622                        });
623
624                        stage_index += 1;
625                    }
626                }
627            }
628        }
629
630        (map_lookups, map_stages)
631    }
632
633    fn add_lookups(
634        &self,
635        lookups: &mut Vec<LookupMap>,
636        table_index: LayoutTableKind,
637        feature_index: u16,
638        variation_index: Option<u32>,
639        lookup_variations: Option<&LookupVariations>,
640        mask: Mask,
641        auto_zwnj: bool,
642        auto_zwj: bool,
643        random: bool,
644        per_syllable: bool,
645        #[cfg(feature = "tracing")] feature_tag: Tag,
646    ) -> Option<()> {
647        let table = self.layout.ot.layout_table(table_index)?;
648
649        let lookup_count = table.lookup_count();
650        let feature = match variation_index {
651            Some(idx) => table
652                .feature_substitution(idx, feature_index)
653                .or_else(|| table.feature(feature_index))?,
654            None => table.feature(feature_index)?,
655        };
656
657        let mut add_lookup = |index: u16| {
658            if index < lookup_count {
659                lookups.push(LookupMap {
660                    index,
661                    auto_zwnj,
662                    auto_zwj,
663                    random,
664                    mask,
665                    per_syllable,
666                    #[cfg(feature = "tracing")]
667                    feature_tag,
668                });
669            }
670        };
671        let indices = feature.lookup_list_indices();
672        let Some(lookup_variations) = lookup_variations else {
673            for index in indices {
674                add_lookup(index.get());
675            }
676            return Some(());
677        };
678        // The feature's lookups at this location: they replace or extend
679        // those of the feature, or of the alternate selected above.
680        let mut resolved: Vec<u16> = indices.iter().map(|index| index.get()).collect();
681        let ot = &self.layout.ot;
682        lookup_variations.apply(
683            feature_index,
684            ot.coords,
685            store_deltas(ot.var_store(), ot.coords),
686            &mut resolved,
687        );
688        for index in resolved {
689            add_lookup(index);
690        }
691
692        Some(())
693    }
694}