| //! A graph for resolving table offsets |
| |
| use font_types::Uint24; |
| |
| use crate::{table_type::TableType, tables::layout::LookupType, write::TableData}; |
| |
| use std::{ |
| collections::{BTreeMap, BTreeSet, BinaryHeap, HashMap, HashSet, VecDeque}, |
| sync::atomic::AtomicU64, |
| }; |
| |
| #[cfg(feature = "dot2")] |
| mod graphviz; |
| mod splitting; |
| |
| static OBJECT_COUNTER: AtomicU64 = AtomicU64::new(0); |
| |
| /// An identifier for an object in the compilation graph. |
| #[derive(Debug, Clone, Copy, PartialOrd, Ord, Hash, PartialEq, Eq)] |
| pub struct ObjectId(u64); |
| |
| #[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)] |
| #[repr(u8)] |
| pub enum OffsetLen { |
| Offset16 = 2, |
| Offset24 = 3, |
| Offset32 = 4, |
| } |
| |
| impl OffsetLen { |
| /// The maximum value for an offset of this length. |
| pub const fn max_value(self) -> u32 { |
| match self { |
| Self::Offset16 => u16::MAX as u32, |
| Self::Offset24 => (1 << 24) - 1, |
| Self::Offset32 => u32::MAX, |
| } |
| } |
| } |
| |
| impl std::fmt::Display for OffsetLen { |
| fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result { |
| match self { |
| Self::Offset16 => write!(f, "Offset16"), |
| Self::Offset24 => write!(f, "Offset24"), |
| Self::Offset32 => write!(f, "Offset32"), |
| } |
| } |
| } |
| /// A ranking used for sorting the graph. |
| /// |
| /// Nodes are assigned a space, and nodes in lower spaces are always |
| /// packed before nodes in higher spaces. |
| #[derive(Debug, Clone, Copy, PartialOrd, Ord, Hash, PartialEq, Eq)] |
| pub struct Space(u32); |
| |
| impl Space { |
| /// A generic space for nodes reachable via 16-bit offsets. |
| const SHORT_REACHABLE: Space = Space(0); |
| /// A generic space for nodes that are reachable via any offset. |
| const REACHABLE: Space = Space(1); |
| /// The first space used for assignment to specific subgraphs. |
| const INIT: Space = Space(2); |
| |
| const fn is_custom(self) -> bool { |
| self.0 >= Space::INIT.0 |
| } |
| } |
| |
| impl ObjectId { |
| pub fn next() -> Self { |
| ObjectId(OBJECT_COUNTER.fetch_add(1, std::sync::atomic::Ordering::Relaxed)) |
| } |
| } |
| |
| #[derive(Debug, Default)] |
| pub(crate) struct ObjectStore { |
| pub(crate) objects: HashMap<TableData, ObjectId>, |
| } |
| |
| impl ObjectStore { |
| pub(crate) fn add(&mut self, data: TableData) -> ObjectId { |
| *self.objects.entry(data).or_insert_with(ObjectId::next) |
| } |
| } |
| |
| /// A graph of subtables, starting at a single root. |
| /// |
| /// This type is used during compilation, to determine the final write order |
| /// for the various subtables. |
| //NOTE: we don't derive Debug because it's way too verbose to be useful |
| pub struct Graph { |
| /// the actual data for each table |
| objects: BTreeMap<ObjectId, TableData>, |
| /// graph-specific state used for sorting |
| nodes: BTreeMap<ObjectId, Node>, |
| order: Vec<ObjectId>, |
| root: ObjectId, |
| parents_invalid: bool, |
| distance_invalid: bool, |
| positions_invalid: bool, |
| next_space: Space, |
| num_roots_per_space: HashMap<Space, usize>, |
| } |
| |
| #[derive(Debug)] |
| struct Node { |
| size: u32, |
| distance: u32, |
| /// overall position after sorting |
| position: u32, |
| space: Space, |
| parents: Vec<(ObjectId, OffsetLen)>, |
| priority: Priority, |
| } |
| |
| /// Scored used when computing shortest distance |
| #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] |
| struct Distance { |
| // a space ranking; like rankings are packed together, |
| // and larger rankings are packed after smaller ones. |
| space: Space, |
| distance: u64, |
| // a tie-breaker, based on order within a parent |
| order: u32, |
| } |
| |
| //TODO: remove me? maybe? not really used right now... |
| #[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord)] |
| struct Priority(u8); |
| |
| /// A record of an overflowing offset |
| #[derive(Clone, Debug)] |
| pub(crate) struct Overflow { |
| parent: ObjectId, |
| child: ObjectId, |
| distance: u32, |
| offset_type: OffsetLen, |
| } |
| |
| impl Priority { |
| const ZERO: Priority = Priority(0); |
| const ONE: Priority = Priority(1); |
| const TWO: Priority = Priority(2); |
| const THREE: Priority = Priority(3); |
| |
| #[cfg(test)] |
| fn increase(&mut self) -> bool { |
| let result = *self != Priority::THREE; |
| self.0 = (self.0 + 1).min(3); |
| result |
| } |
| } |
| |
| impl Distance { |
| const ROOT: Distance = Distance { |
| space: Space::SHORT_REACHABLE, |
| distance: 0, |
| order: 0, |
| }; |
| |
| fn rev(self) -> std::cmp::Reverse<Distance> { |
| std::cmp::Reverse(self) |
| } |
| } |
| |
| impl Node { |
| pub fn new(size: u32) -> Self { |
| Node { |
| //obj, |
| size, |
| position: Default::default(), |
| distance: Default::default(), |
| space: Space::REACHABLE, |
| parents: Default::default(), |
| priority: Default::default(), |
| } |
| } |
| |
| #[cfg(test)] |
| fn raise_priority(&mut self) -> bool { |
| self.priority.increase() |
| } |
| |
| fn modified_distance(&self, order: u32) -> Distance { |
| let prev_dist = self.distance as i64; |
| let distance = match self.priority { |
| Priority::ZERO => prev_dist, |
| Priority::ONE => prev_dist - self.size as i64 / 2, |
| Priority::TWO => prev_dist - self.size as i64, |
| Priority::THREE => 0, |
| _ => 0, |
| } |
| .max(0) as u64; |
| |
| Distance { |
| space: self.space, |
| distance, |
| order, |
| } |
| } |
| } |
| |
| impl Graph { |
| pub(crate) fn from_obj_store(store: ObjectStore, root: ObjectId) -> Self { |
| let objects = store.objects.into_iter().map(|(k, v)| (v, k)).collect(); |
| Self::from_objects(objects, root) |
| } |
| |
| fn from_objects(objects: BTreeMap<ObjectId, TableData>, root: ObjectId) -> Self { |
| let nodes = objects |
| .iter() |
| //TODO: ensure table sizes elsewhere? |
| .map(|(key, obj)| (*key, Node::new(obj.bytes.len().try_into().unwrap()))) |
| .collect(); |
| Graph { |
| objects, |
| nodes, |
| order: Default::default(), |
| root, |
| parents_invalid: true, |
| distance_invalid: true, |
| positions_invalid: true, |
| next_space: Space::INIT, |
| num_roots_per_space: Default::default(), |
| } |
| } |
| |
| /// Write out the serialized graph. |
| /// |
| /// This is not public API, and you are responsible for ensuring that |
| /// the graph is sorted before calling (by calling `pack_objects`, and |
| /// checking that it has succeeded). |
| pub(crate) fn serialize(&self) -> Vec<u8> { |
| fn write_offset(at: &mut [u8], len: OffsetLen, resolved: u32) { |
| let at = &mut at[..len as u8 as usize]; |
| match len { |
| OffsetLen::Offset16 => at.copy_from_slice( |
| u16::try_from(resolved) |
| .expect("offset overflow should be checked before now") |
| .to_be_bytes() |
| .as_slice(), |
| ), |
| OffsetLen::Offset24 => at.copy_from_slice( |
| Uint24::checked_new(resolved) |
| .expect("offset overflow should be checked before now") |
| .to_be_bytes() |
| .as_slice(), |
| ), |
| OffsetLen::Offset32 => at.copy_from_slice(resolved.to_be_bytes().as_slice()), |
| } |
| } |
| |
| assert!( |
| !self.order.is_empty(), |
| "graph must be sorted before serialization" |
| ); |
| let mut offsets = HashMap::new(); |
| let mut out = Vec::new(); |
| let mut off = 0; |
| |
| // first pass: write out bytes, record positions of offsets |
| for id in &self.order { |
| let node = self.objects.get(id).unwrap(); |
| offsets.insert(*id, off); |
| off += node.bytes.len() as u32; |
| out.extend_from_slice(&node.bytes); |
| } |
| |
| // second pass: write offsets |
| let mut table_head = 0; |
| for id in &self.order { |
| let node = self.objects.get(id).unwrap(); |
| for offset in &node.offsets { |
| let abs_off = *offsets |
| .get(&offset.object) |
| .expect("all offsets visited in first pass"); |
| let rel_off = abs_off - (table_head + offset.adjustment); |
| let buffer_pos = table_head + offset.pos; |
| let write_over = out.get_mut(buffer_pos as usize..).unwrap(); |
| write_offset(write_over, offset.len, rel_off); |
| } |
| table_head += node.bytes.len() as u32; |
| } |
| out |
| } |
| |
| /// Attempt to pack the graph. |
| /// |
| /// This involves finding an order for objects such that all offsets are |
| /// resolveable. |
| /// |
| /// In the simple case, this just means finding a topological ordering. |
| /// In exceptional cases, however, this may require us to significantly |
| /// modify the graph. |
| /// |
| /// Our implementation is closely modeled on the implementation in the |
| /// HarfBuzz repacker; see the [repacker docs] for further detail. |
| /// |
| /// returns `true` if a solution is found, `false` otherwise |
| /// |
| /// [repacker docs]: https://github.com/harfbuzz/harfbuzz/blob/main/docs/repacker.md |
| pub(crate) fn pack_objects(&mut self) -> bool { |
| if self.basic_sort() { |
| return true; |
| } |
| |
| self.try_splitting_subtables(); |
| self.try_promoting_subtables(); |
| |
| log::info!("assigning spaces"); |
| self.assign_spaces_hb(); |
| self.sort_shortest_distance(); |
| |
| if !self.has_overflows() { |
| return true; |
| } |
| |
| // now isolate spaces in a loop, until there are no more left: |
| let overflows = loop { |
| let overflows = self.find_overflows(); |
| if overflows.is_empty() { |
| // we're done |
| return true; |
| } |
| log::trace!( |
| "failed with {} overflows, current size {}", |
| overflows.len(), |
| self.debug_len() |
| ); |
| if !self.try_isolating_subgraphs(&overflows) { |
| log::debug!("finished isolating all subgraphs without solution"); |
| break overflows; |
| } |
| self.sort_shortest_distance(); |
| }; |
| |
| assert!(!overflows.is_empty()); |
| self.debug_overflows(&overflows); |
| false |
| } |
| |
| /// Initial sorting operation. Attempt Kahn, falling back to shortest distance. |
| /// |
| /// This has to be called first, since it establishes an initial order. |
| /// subsequent operations on the graph require this order. |
| /// |
| /// returns `true` if sort succeeds with no overflows |
| fn basic_sort(&mut self) -> bool { |
| log::trace!("sorting {} objects", self.objects.len()); |
| |
| self.sort_kahn(); |
| if !self.has_overflows() { |
| return true; |
| } |
| log::trace!("kahn failed, trying shortest distance"); |
| self.sort_shortest_distance(); |
| !self.has_overflows() |
| } |
| |
| fn has_overflows(&self) -> bool { |
| for (parent_id, data) in &self.objects { |
| let parent = &self.nodes[parent_id]; |
| for link in &data.offsets { |
| let child = &self.nodes[&link.object]; |
| //TODO: account for 'whence' |
| let rel_off = child.position - parent.position; |
| if link.len.max_value() < rel_off { |
| return true; |
| } |
| } |
| } |
| false |
| } |
| |
| pub(crate) fn find_overflows(&self) -> Vec<Overflow> { |
| let mut result = Vec::new(); |
| for (parent_id, data) in &self.objects { |
| let parent = &self.nodes[parent_id]; |
| for link in &data.offsets { |
| let child = &self.nodes[&link.object]; |
| //TODO: account for 'whence' |
| let rel_off = child.position - parent.position; |
| if link.len.max_value() < rel_off { |
| result.push(Overflow { |
| parent: *parent_id, |
| child: link.object, |
| distance: rel_off, |
| offset_type: link.len, |
| }); |
| } |
| } |
| } |
| result |
| } |
| |
| fn debug_overflows(&self, overflows: &[Overflow]) { |
| let (parents, children): (HashSet<_>, HashSet<_>) = |
| overflows.iter().map(|x| (x.parent, x.child)).unzip(); |
| log::debug!( |
| "found {} overflows from {} parents to {} children", |
| overflows.len(), |
| parents.len(), |
| children.len() |
| ); |
| |
| for overflow in overflows { |
| log::debug!( |
| "{:?} -> {:?} type {} dist {}", |
| overflow.parent, |
| overflow.child, |
| overflow.offset_type, |
| overflow.distance |
| ); |
| } |
| } |
| |
| // only valid if order is up to date. Returns total byte len of graph. |
| fn debug_len(&self) -> usize { |
| self.order |
| .iter() |
| .map(|id| self.objects.get(id).unwrap().bytes.len()) |
| .sum() |
| } |
| |
| fn update_parents(&mut self) { |
| if !self.parents_invalid { |
| return; |
| } |
| for node in self.nodes.values_mut() { |
| node.parents.clear(); |
| } |
| |
| for (id, obj) in &self.objects { |
| for link in &obj.offsets { |
| self.nodes |
| .get_mut(&link.object) |
| .unwrap() |
| .parents |
| .push((*id, link.len)); |
| } |
| } |
| self.parents_invalid = false; |
| } |
| |
| fn remove_orphans(&mut self) { |
| let mut visited = HashSet::with_capacity(self.nodes.len()); |
| self.find_subgraph_hb(self.root, &mut visited); |
| if visited.len() != self.nodes.len() { |
| log::info!("removing {} orphan nodes", self.nodes.len() - visited.len()); |
| for id in self |
| .nodes |
| .keys() |
| .copied() |
| .collect::<HashSet<_>>() |
| .difference(&visited) |
| { |
| self.nodes.remove(id); |
| self.objects.remove(id); |
| } |
| } |
| } |
| |
| fn sort_kahn(&mut self) { |
| self.positions_invalid = true; |
| if self.nodes.len() <= 1 { |
| self.order.extend(self.nodes.keys().copied()); |
| return; |
| } |
| |
| let mut queue = BinaryHeap::new(); |
| let mut removed_edges = HashMap::new(); |
| let mut current_pos: u32 = 0; |
| self.order.clear(); |
| |
| self.update_parents(); |
| queue.push(std::cmp::Reverse(self.root)); |
| |
| while let Some(id) = queue.pop().map(|x| x.0) { |
| let next = &self.objects[&id]; |
| self.order.push(id); |
| self.nodes.get_mut(&id).unwrap().position = current_pos; |
| current_pos += next.bytes.len() as u32; |
| for link in &next.offsets { |
| let seen_edges = removed_edges.entry(link.object).or_insert(0usize); |
| *seen_edges += 1; |
| // if the target of this link has no other incoming links, add |
| // to the queue |
| if *seen_edges == self.nodes[&link.object].parents.len() { |
| queue.push(std::cmp::Reverse(link.object)); |
| } |
| } |
| } |
| //TODO: check for orphans & cycles? |
| for (id, seen_len) in &removed_edges { |
| if *seen_len != self.nodes[id].parents.len() { |
| panic!("cycle or something?"); |
| } |
| } |
| } |
| |
| pub(crate) fn sort_shortest_distance(&mut self) { |
| self.positions_invalid = true; |
| self.update_parents(); |
| self.update_distances(); |
| self.assign_space_0(); |
| |
| let mut queue = BinaryHeap::new(); |
| let mut removed_edges = HashMap::with_capacity(self.nodes.len()); |
| let mut current_pos = 0; |
| self.order.clear(); |
| |
| queue.push((Distance::ROOT.rev(), self.root)); |
| let mut obj_order = 1u32; |
| while let Some((_, id)) = queue.pop() { |
| let next = &self.objects[&id]; |
| self.order.push(id); |
| self.nodes.get_mut(&id).unwrap().position = current_pos; |
| current_pos += next.bytes.len() as u32; |
| for link in &next.offsets { |
| let seen_edges = removed_edges.entry(link.object).or_insert(0usize); |
| *seen_edges += 1; |
| // if the target of this link has no other incoming links, add |
| // to the queue |
| if *seen_edges == self.nodes[&link.object].parents.len() { |
| let distance = self.nodes[&link.object].modified_distance(obj_order); |
| obj_order += 1; |
| queue.push((distance.rev(), link.object)); |
| } |
| } |
| } |
| |
| //TODO: check for orphans & cycles? |
| for (id, seen_len) in &removed_edges { |
| if *seen_len != self.nodes[id].parents.len() { |
| panic!("cycle or something?"); |
| } |
| } |
| } |
| |
| fn update_distances(&mut self) { |
| self.nodes |
| .values_mut() |
| .for_each(|node| node.distance = u32::MAX); |
| self.nodes.get_mut(&self.root).unwrap().distance = u32::MIN; |
| |
| let mut queue = BinaryHeap::new(); |
| let mut visited = HashSet::new(); |
| queue.push((Default::default(), self.root)); |
| |
| while let Some((_, next_id)) = queue.pop() { |
| if !visited.insert(next_id) { |
| continue; |
| } |
| let next_distance = self.nodes[&next_id].distance; |
| let next_obj = &self.objects[&next_id]; |
| for link in &next_obj.offsets { |
| if visited.contains(&link.object) { |
| continue; |
| } |
| |
| let child = self.nodes.get_mut(&link.object).unwrap(); |
| let child_distance = next_distance + child.size; |
| |
| if child_distance < child.distance { |
| child.distance = child_distance; |
| queue.push((child_distance, link.object)); |
| } |
| } |
| } |
| |
| self.distance_invalid = false; |
| } |
| |
| /// isolate and assign spaces to subgraphs reachable via long offsets. |
| /// |
| /// This finds all subgraphs that are reachable via long offsets, and |
| /// isolates them (ensuring they are *only* reachable via long offsets), |
| /// assigning each unique space an identifier. |
| /// |
| /// Each space may have multiple roots; this works by finding the connected |
| /// components from each root (counting only nodes reachable via long offsets). |
| /// |
| /// This is a close port of the [assign_spaces] method used by the HarfBuzz |
| /// repacker. |
| /// |
| /// [assign_spaces]: https://github.com/harfbuzz/harfbuzz/blob/main/src/graph/graph.hh#L624 |
| fn assign_spaces_hb(&mut self) -> bool { |
| self.update_parents(); |
| let (visited, mut roots) = self.find_space_roots_hb(); |
| |
| if roots.is_empty() { |
| return false; |
| } |
| |
| log::trace!("found {} space roots to isolate", roots.len()); |
| |
| // we want to *invert* the visited set, but we don't have a fancy hb_set_t |
| let mut visited = self |
| .order |
| .iter() |
| .copied() |
| .collect::<HashSet<_>>() |
| .difference(&visited) |
| .copied() |
| .collect::<HashSet<_>>(); |
| |
| let mut connected_roots = BTreeSet::new(); // we can reuse this |
| while let Some(next) = roots.iter().copied().next() { |
| connected_roots.clear(); |
| self.find_connected_nodes_hb(next, &mut roots, &mut visited, &mut connected_roots); |
| self.isolate_subgraph_hb(&mut connected_roots); |
| |
| self.distance_invalid = true; |
| self.positions_invalid = true; |
| } |
| true |
| } |
| |
| /// Find the root nodes of 32 (and later 24?)-bit space. |
| /// |
| /// These are the set of nodes that have incoming long offsets, for which |
| /// no ancestor has an incoming long offset. |
| /// |
| /// Ported from the [find_space_roots] method in HarfBuzz. |
| /// |
| /// [find_space_roots]: https://github.com/harfbuzz/harfbuzz/blob/main/src/graph/graph.hh#L508 |
| fn find_space_roots_hb(&self) -> (HashSet<ObjectId>, BTreeSet<ObjectId>) { |
| let mut visited = HashSet::new(); |
| let mut roots = BTreeSet::new(); |
| |
| let mut queue = VecDeque::from([self.root]); |
| |
| while let Some(id) = queue.pop_front() { |
| if visited.contains(&id) { |
| continue; |
| } |
| let obj = self.objects.get(&id).unwrap(); |
| for link in &obj.offsets { |
| //FIXME: harfbuzz has a bunch of logic here for 24-bit offsets |
| if link.len == OffsetLen::Offset32 { |
| roots.insert(link.object); |
| self.find_subgraph_hb(link.object, &mut visited); |
| } else { |
| queue.push_back(link.object); |
| } |
| } |
| } |
| (visited, roots) |
| } |
| |
| fn find_subgraph_hb(&self, idx: ObjectId, nodes: &mut HashSet<ObjectId>) { |
| if !nodes.insert(idx) { |
| return; |
| } |
| for link in self.objects.get(&idx).unwrap().offsets.iter() { |
| self.find_subgraph_hb(link.object, nodes); |
| } |
| } |
| |
| fn find_subgraph_map_hb(&self, idx: ObjectId, graph: &mut BTreeMap<ObjectId, usize>) { |
| use std::collections::btree_map::Entry; |
| for link in &self.objects[&idx].offsets { |
| match graph.entry(link.object) { |
| // To avoid double counting, we only recurse if we are seeing |
| // this node for the first time. |
| Entry::Vacant(entry) => { |
| entry.insert(1); |
| self.find_subgraph_map_hb(link.object, graph); |
| } |
| Entry::Occupied(entry) => { |
| *entry.into_mut() += 1; |
| } |
| } |
| } |
| } |
| |
| /// find all of the members of 'targets' that are reachable, skipping nodes in `visited`. |
| fn find_connected_nodes_hb( |
| &self, |
| id: ObjectId, |
| targets: &mut BTreeSet<ObjectId>, |
| visited: &mut HashSet<ObjectId>, |
| connected: &mut BTreeSet<ObjectId>, |
| ) { |
| if !visited.insert(id) { |
| return; |
| } |
| if targets.remove(&id) { |
| connected.insert(id); |
| } |
| // recurse to all children and parents |
| for (obj, _) in &self.nodes.get(&id).unwrap().parents { |
| self.find_connected_nodes_hb(*obj, targets, visited, connected); |
| } |
| for link in &self.objects.get(&id).unwrap().offsets { |
| self.find_connected_nodes_hb(link.object, targets, visited, connected); |
| } |
| } |
| |
| /// Isolate the subgraph with the provided roots, moving it to a new space. |
| /// |
| /// This duplicates any nodes in this subgraph that are shared with |
| /// any other nodes in the graph. |
| /// |
| /// Based on the [isolate_subgraph] method in HarfBuzz. |
| /// |
| /// [isolate_subgraph]: https://github.com/harfbuzz/harfbuzz/blob/main/src/graph/graph.hh#L508 |
| fn isolate_subgraph_hb(&mut self, roots: &mut BTreeSet<ObjectId>) -> bool { |
| self.update_parents(); |
| |
| // map of object id -> number of incoming edges |
| let mut subgraph = BTreeMap::new(); |
| |
| for root in roots.iter() { |
| // for the roots, we set the edge count to the number of long |
| // incoming offsets; if this differs from the total number of |
| // incoming offsets it means we need to dupe the root as well. |
| let inbound_wide_offsets = self.nodes[root] |
| .parents |
| .iter() |
| .filter(|(_, len)| !matches!(len, OffsetLen::Offset16)) |
| .count(); |
| subgraph.insert(*root, inbound_wide_offsets); |
| self.find_subgraph_map_hb(*root, &mut subgraph); |
| } |
| |
| let next_space = self.next_space(); |
| log::debug!("moved {} roots to {next_space:?}", roots.len(),); |
| self.num_roots_per_space.insert(next_space, roots.len()); |
| let mut id_map = HashMap::new(); |
| for (id, incoming_edges_in_subgraph) in &subgraph { |
| // there are edges to this object from outside the subgraph; dupe it. |
| if *incoming_edges_in_subgraph < self.nodes[id].parents.len() { |
| self.duplicate_subgraph(*id, &mut id_map, next_space); |
| } |
| } |
| |
| // now remap any links in the subgraph from nodes that were not |
| // themselves duplicated (since they were not reachable from outside) |
| for id in subgraph.keys().filter(|k| !id_map.contains_key(k)) { |
| self.nodes.get_mut(id).unwrap().space = next_space; |
| let obj = self.objects.get_mut(id).unwrap(); |
| for link in &mut obj.offsets { |
| if let Some(new_id) = id_map.get(&link.object) { |
| link.object = *new_id; |
| } |
| } |
| } |
| |
| if id_map.is_empty() { |
| return false; |
| } |
| |
| // now everything but the links to the roots roots has been remapped; |
| // remap those, if needed |
| for root in roots.iter() { |
| let Some(new_id) = id_map.get(root) else { |
| continue; |
| }; |
| self.parents_invalid = true; |
| self.positions_invalid = true; |
| for (parent_id, len) in &self.nodes[new_id].parents { |
| if !matches!(len, OffsetLen::Offset16) { |
| for link in &mut self.objects.get_mut(parent_id).unwrap().offsets { |
| if link.object == *root { |
| link.object = *new_id; |
| } |
| } |
| } |
| } |
| } |
| |
| // if any roots changed, we also rename them in the input set: |
| for (old, new) in id_map { |
| if roots.remove(&old) { |
| roots.insert(new); |
| } |
| } |
| |
| true |
| } |
| |
| /// for each space that has overflows and > 1 roots, select half the roots |
| /// and move them to a separate subgraph. |
| // |
| /// return `true` if any change was made. |
| /// |
| /// This is a port of the [_try_isolating_subgraphs] method in hb-repacker. |
| /// |
| /// [_try_isolating_subgraphs]: https://github.com/harfbuzz/harfbuzz/blob/main/src/hb-repacker.hh#L182 |
| fn try_isolating_subgraphs(&mut self, overflows: &[Overflow]) -> bool { |
| let mut to_isolate = BTreeMap::new(); |
| for overflow in overflows { |
| let parent_space = self.nodes[&overflow.parent].space; |
| // we only isolate subgraphs in wide-space |
| if !parent_space.is_custom() || self.num_roots_per_space[&parent_space] < 2 { |
| continue; |
| } |
| // if parent space is custom it means all children should also be |
| // in the same custom space. |
| assert_eq!(parent_space, self.nodes[&overflow.child].space); |
| let root = self.find_root_of_space(overflow.parent); |
| assert_eq!(self.nodes[&root].space, parent_space); |
| to_isolate |
| .entry(parent_space) |
| .or_insert_with(BTreeSet::new) |
| .insert(root); |
| } |
| |
| if to_isolate.is_empty() { |
| return false; |
| } |
| |
| for (space, mut roots) in to_isolate { |
| let n_total_roots = self.num_roots_per_space[&space]; |
| debug_assert!(n_total_roots >= 2, "checked in the loop above"); |
| let max_to_move = n_total_roots / 2; |
| log::trace!( |
| "moving {} of {} candidate roots from {space:?} to new space", |
| max_to_move.min(roots.len()), |
| roots.len() |
| ); |
| while roots.len() > max_to_move { |
| roots.pop_last(); |
| } |
| self.isolate_subgraph_hb(&mut roots); |
| *self.num_roots_per_space.get_mut(&space).unwrap() -= roots.len(); |
| } |
| |
| true |
| } |
| |
| // invariant: obj must not be in space 0 |
| fn find_root_of_space(&self, obj: ObjectId) -> ObjectId { |
| let space = self.nodes[&obj].space; |
| debug_assert!(space.is_custom()); |
| let parent = self.nodes[&obj].parents[0].0; |
| if self.nodes[&parent].space != space { |
| return obj; |
| } |
| self.find_root_of_space(parent) |
| } |
| |
| fn next_space(&mut self) -> Space { |
| self.next_space = Space(self.next_space.0 + 1); |
| self.next_space |
| } |
| |
| fn try_promoting_subtables(&mut self) { |
| let Some((can_promote, parent_id)) = self.get_promotable_subtables() else { |
| return; |
| }; |
| let to_promote = self.select_promotions_hb(&can_promote, parent_id); |
| log::info!( |
| "promoting {} of {} eligible subtables", |
| to_promote.len(), |
| can_promote.len() |
| ); |
| self.actually_promote_subtables(&to_promote); |
| } |
| |
| fn actually_promote_subtables(&mut self, to_promote: &[ObjectId]) { |
| fn make_extension(type_: LookupType, subtable_id: ObjectId) -> TableData { |
| const EXT_FORMAT: u16 = 1; |
| let mut data = TableData::new(TableType::Named("ExtensionPosFormat1")); |
| data.write(EXT_FORMAT); |
| data.write(type_.to_raw()); |
| data.add_offset(subtable_id, 4, 0); |
| data |
| } |
| |
| for id in to_promote { |
| // 'id' is a lookup table. |
| // we need to: |
| // - change the subtable type |
| // - create a new extension table for each subtable |
| // - update the object ids |
| |
| let mut lookup = self.objects.remove(id).unwrap(); |
| let lookup_type = lookup.type_.to_lookup_type().expect("validated before now"); |
| for subtable_ref in &mut lookup.offsets { |
| let ext_table = make_extension(lookup_type, subtable_ref.object); |
| let ext_id = self.add_object(ext_table); |
| subtable_ref.object = ext_id; |
| } |
| lookup.write_over(lookup_type.promote().to_raw(), 0); |
| lookup.type_ = lookup_type.promote().into(); |
| self.objects.insert(*id, lookup); |
| } |
| self.parents_invalid = true; |
| self.positions_invalid = true; |
| } |
| |
| /// Manually add an object to the graph, after initial compilation. |
| /// |
| /// This can be used to perform edits to the graph during compilation, such |
| /// as for table splitting or promotion. |
| /// |
| /// This has drawbacks; in particular, at this stage we no longer deduplicate |
| /// objects. |
| fn add_object(&mut self, data: TableData) -> ObjectId { |
| self.parents_invalid = true; |
| self.distance_invalid = true; |
| |
| let id = ObjectId::next(); |
| self.nodes.insert(id, Node::new(data.bytes.len() as _)); |
| self.objects.insert(id, data); |
| id |
| } |
| |
| // get the list of tables that can be promoted, as well as the id of their parent table |
| fn get_promotable_subtables(&self) -> Option<(Vec<ObjectId>, ObjectId)> { |
| let can_promote = self |
| .objects |
| .iter() |
| .filter_map(|(id, obj)| (obj.type_.is_promotable()).then_some(*id)) |
| .collect::<Vec<_>>(); |
| |
| if can_promote.is_empty() { |
| return None; |
| } |
| |
| // sanity check: ensure that all promotable tables have a common root. |
| let parents = can_promote |
| .iter() |
| .flat_map(|id| { |
| self.nodes |
| .get(id) |
| .expect("all nodes exist") |
| .parents |
| .iter() |
| .map(|x| x.0) |
| }) |
| .collect::<HashSet<_>>(); |
| |
| // the only promotable subtables should be lookups, and there should |
| // be a single LookupList that is their parent; if there is more than |
| // one parent then something weird is going on. |
| if parents.len() > 1 { |
| if cfg!(debug_assertions) { |
| panic!("Promotable subtables exist with multiple parents"); |
| } else { |
| log::warn!("Promotable subtables exist with multiple parents"); |
| return None; |
| } |
| } |
| |
| let parent_id = *parents.iter().next().unwrap(); |
| Some((can_promote, parent_id)) |
| } |
| |
| /// select the tables to promote to extension, harfbuzz algorithm |
| /// |
| /// Based on the logic in HarfBuzz's [`_promote_exetnsions_if_needed`][hb-promote][hb-promote] function. |
| /// |
| /// [hb-promote]: https://github.com/harfbuzz/harfbuzz/blob/5d543d64222c6ce45332d0c188790f90691ef112/src/hb-repacker.hh#L97 |
| fn select_promotions_hb(&self, candidates: &[ObjectId], parent_id: ObjectId) -> Vec<ObjectId> { |
| struct LookupSize { |
| id: ObjectId, |
| subgraph_size: usize, |
| subtable_count: usize, |
| } |
| |
| impl LookupSize { |
| // I could impl Ord but then I need to impl PartialEq and it ends |
| // up being way more code |
| fn sort_key(&self) -> impl Ord { |
| let bytes_per_subtable = self.subtable_count as f64 / self.subgraph_size as f64; |
| // f64 isn't ord, so we turn it into an integer, |
| // then reverse, because we want bigger things first |
| std::cmp::Reverse((bytes_per_subtable * 1e9) as u64) |
| } |
| } |
| |
| let mut lookup_sizes = Vec::with_capacity(candidates.len()); |
| let mut reusable_buffer = HashSet::new(); |
| let mut queue = VecDeque::new(); |
| for id in candidates { |
| // get the subgraph size |
| queue.clear(); |
| queue.push_back(*id); |
| let subgraph_size = self.find_subgraph_size(&mut queue, &mut reusable_buffer); |
| let subtable_count = self.objects.get(id).unwrap().offsets.len(); |
| lookup_sizes.push(LookupSize { |
| id: *id, |
| subgraph_size, |
| subtable_count, |
| }); |
| } |
| |
| lookup_sizes.sort_by_key(LookupSize::sort_key); |
| const EXTENSION_SIZE: usize = 8; // number of bytes added by an extension subtable |
| const MAX_LAYER_SIZE: usize = u16::MAX as usize; |
| |
| let lookup_list_size = self.objects.get(&parent_id).unwrap().bytes.len(); |
| let mut l2_l3_size = lookup_list_size; // size of LookupList + lookups |
| let mut l3_l4_size = 0; // Lookups + lookup subtables |
| let mut l4_plus_size = 0; // subtables and anything below that |
| |
| // start by assuming all lookups are extensions; we will adjust this later |
| // if we do not promote. |
| for lookup in &lookup_sizes { |
| let subtables_size = lookup.subtable_count * EXTENSION_SIZE; |
| l3_l4_size += subtables_size; |
| l4_plus_size += subtables_size; |
| } |
| |
| let mut layers_full = false; |
| let mut to_promote = Vec::new(); |
| for lookup in &lookup_sizes { |
| if !layers_full { |
| let lookup_size = self.objects.get(&lookup.id).unwrap().bytes.len(); |
| let subtables_size = self.find_children_size(lookup.id); |
| let remaining_size = lookup.subgraph_size - lookup_size - subtables_size; |
| l2_l3_size += lookup_size; |
| l3_l4_size += lookup_size + subtables_size; |
| // adjust down, because we are demoting out of extension space |
| l3_l4_size -= lookup.subtable_count * EXTENSION_SIZE; |
| l4_plus_size += subtables_size + remaining_size; |
| |
| if l2_l3_size < MAX_LAYER_SIZE |
| && l3_l4_size < MAX_LAYER_SIZE |
| && l4_plus_size < MAX_LAYER_SIZE |
| { |
| // this lookup fits in the 16-bit space, great |
| continue; |
| } |
| layers_full = true; |
| } |
| to_promote.push(lookup.id); |
| } |
| to_promote |
| } |
| |
| /// See if we have any subtables that support splitting, and split them |
| /// if needed. |
| /// |
| /// Based on [`_presplit_subtables_if_needed`][presplit] in hb-repacker |
| /// |
| /// [presplit]: https://github.com/harfbuzz/harfbuzz/blob/5d543d64222c6ce45332d0c188790f90691ef112/src/hb-repacker.hh#LL72C22-L72C22 |
| fn try_splitting_subtables(&mut self) { |
| let splittable = self |
| .objects |
| .iter() |
| .filter_map(|(id, obj)| obj.type_.is_splittable().then_some(*id)) |
| .collect::<Vec<_>>(); |
| for lookup in &splittable { |
| self.split_subtables_if_needed(*lookup); |
| } |
| if !splittable.is_empty() { |
| self.remove_orphans(); |
| } |
| } |
| |
| fn split_subtables_if_needed(&mut self, lookup: ObjectId) { |
| // So You Want to Split Subtables: |
| // - support PairPos and MarkBase. |
| let type_ = self.objects[&lookup].type_; |
| match type_ { |
| TableType::GposLookup(LookupType::PAIR_POS) => splitting::split_pair_pos(self, lookup), |
| TableType::GposLookup(LookupType::MARK_TO_BASE) => { |
| splitting::split_mark_to_base(self, lookup) |
| } |
| _ => (), |
| } |
| } |
| |
| /// the size only of children of this object, not the whole subgraph |
| fn find_children_size(&self, id: ObjectId) -> usize { |
| self.objects[&id] |
| .offsets |
| .iter() |
| .map(|off| self.objects.get(&off.object).unwrap().bytes.len()) |
| .sum() |
| } |
| |
| fn find_subgraph_size( |
| &self, |
| queue: &mut VecDeque<ObjectId>, |
| visited: &mut HashSet<ObjectId>, |
| ) -> usize { |
| let mut size = 0; |
| visited.clear(); |
| while !queue.is_empty() { |
| let next = queue.pop_front().unwrap(); |
| visited.insert(next); |
| let obj = self.objects.get(&next).unwrap(); |
| size += obj.bytes.len(); |
| queue.extend( |
| obj.offsets |
| .iter() |
| .filter_map(|obj| (!visited.contains(&obj.object)).then_some(obj.object)), |
| ); |
| } |
| size |
| } |
| |
| fn duplicate_subgraph( |
| &mut self, |
| root: ObjectId, |
| dupes: &mut HashMap<ObjectId, ObjectId>, |
| space: Space, |
| ) -> ObjectId { |
| if let Some(existing) = dupes.get(&root) { |
| return *existing; |
| } |
| self.parents_invalid = true; |
| self.distance_invalid = true; |
| let new_root = ObjectId::next(); |
| log::trace!("duplicating node {root:?} to {new_root:?}"); |
| |
| let mut obj = self.objects.get(&root).cloned().unwrap(); |
| let mut node = Node::new(obj.bytes.len() as u32); |
| node.space = space; |
| |
| for link in &mut obj.offsets { |
| // recursively duplicate the object |
| link.object = self.duplicate_subgraph(link.object, dupes, space); |
| } |
| dupes.insert(root, new_root); |
| self.objects.insert(new_root, obj); |
| self.nodes.insert(new_root, node); |
| new_root |
| } |
| |
| /// Find the set of nodes that are reachable from root only following |
| /// 16 & 24 bit offsets, and assign them to space 0. |
| fn assign_space_0(&mut self) { |
| let mut stack = VecDeque::from([self.root]); |
| |
| while let Some(next) = stack.pop_front() { |
| match self.nodes.get_mut(&next) { |
| Some(node) if node.space != Space::SHORT_REACHABLE => { |
| node.space = Space::SHORT_REACHABLE |
| } |
| _ => continue, |
| } |
| for link in self |
| .objects |
| .get(&next) |
| .iter() |
| .flat_map(|obj| obj.offsets.iter()) |
| { |
| if link.len != OffsetLen::Offset32 { |
| stack.push_back(link.object); |
| } |
| } |
| } |
| } |
| |
| #[cfg(test)] |
| fn find_descendents(&self, root: ObjectId) -> HashSet<ObjectId> { |
| let mut result = HashSet::new(); |
| let mut stack = VecDeque::from([root]); |
| while let Some(id) = stack.pop_front() { |
| if result.insert(id) { |
| for link in self |
| .objects |
| .get(&id) |
| .iter() |
| .flat_map(|obj| obj.offsets.iter()) |
| { |
| stack.push_back(link.object); |
| } |
| } |
| } |
| result |
| } |
| |
| #[cfg(feature = "dot2")] |
| pub(crate) fn write_graph_viz(&self, path: impl AsRef<std::path::Path>) -> std::io::Result<()> { |
| // if this is set then we prune the generated graph |
| const PRUNE_GRAPH_ENV_VAR: &str = "FONTC_PRUNE_GRAPH"; |
| let try_trim_graph = std::env::var_os(PRUNE_GRAPH_ENV_VAR).is_some(); |
| graphviz::GraphVizGraph::from_graph(self, try_trim_graph).write_to_file(path) |
| } |
| } |
| |
| impl Default for Priority { |
| fn default() -> Self { |
| Priority::ZERO |
| } |
| } |
| |
| #[cfg(test)] |
| mod tests { |
| use std::ops::Range; |
| |
| use font_types::GlyphId16; |
| |
| use crate::TableWriter; |
| |
| use super::*; |
| |
| fn make_ids<const N: usize>() -> [ObjectId; N] { |
| let mut ids = [ObjectId::next(); N]; |
| for id in ids.iter_mut().skip(1) { |
| *id = ObjectId::next(); |
| } |
| ids |
| } |
| |
| struct Link { |
| from: ObjectId, |
| to: ObjectId, |
| width: OffsetLen, |
| } |
| |
| struct TestGraphBuilder { |
| objects: Vec<(ObjectId, usize)>, |
| links: Vec<Link>, |
| } |
| |
| impl TestGraphBuilder { |
| fn new<const N: usize>(ids: [ObjectId; N], sizes: [usize; N]) -> Self { |
| TestGraphBuilder { |
| objects: ids.into_iter().zip(sizes).collect(), |
| links: Default::default(), |
| } |
| } |
| |
| fn add_link(&mut self, from: ObjectId, to: ObjectId, width: OffsetLen) -> &mut Self { |
| self.links.push(Link { from, to, width }); |
| self |
| } |
| |
| fn build(&self) -> Graph { |
| let mut objects = self |
| .objects |
| .iter() |
| .map(|(id, size)| { |
| let table = TableData::make_mock(*size); |
| (*id, table) |
| }) |
| .collect::<BTreeMap<_, _>>(); |
| |
| for link in &self.links { |
| objects |
| .get_mut(&link.from) |
| .unwrap() |
| .add_mock_offset(link.to, link.width); |
| } |
| let root = self.objects.first().unwrap().0; |
| Graph::from_objects(objects, root) |
| } |
| } |
| |
| //#[test] |
| //fn difference_smoke_test() { |
| //assert!(Distance::MIN < Distance::MAX); |
| //assert!( |
| //Distance::from_offset_and_size(OffsetLen::Offset16, 10) |
| //< Distance::from_offset_and_size(OffsetLen::Offset16, 20) |
| //); |
| //assert!( |
| //Distance::from_offset_and_size(OffsetLen::Offset32, 10) |
| //> Distance::from_offset_and_size(OffsetLen::Offset16, 20) |
| //); |
| //assert!(Distance::new(10, 3) > Distance::new(10, 1)); |
| //} |
| |
| #[test] |
| fn priority_smoke_test() { |
| let mut node = Node::new(20); |
| node.distance = 100; |
| let mod0 = node.modified_distance(1); |
| node.raise_priority(); |
| let mod1 = node.modified_distance(1); |
| assert!(mod0 > mod1); |
| node.raise_priority(); |
| let mod2 = node.modified_distance(1); |
| assert!(mod1 > mod2); |
| node.raise_priority(); |
| let mod3 = node.modified_distance(1); |
| assert!(mod2 > mod3, "{mod2:?} {mod3:?}"); |
| |
| // max priority is 3 |
| node.raise_priority(); |
| let mod4 = node.modified_distance(1); |
| assert_eq!(mod3, mod4); |
| } |
| |
| #[test] |
| fn kahn_basic() { |
| let ids = make_ids::<4>(); |
| let sizes = [10, 10, 20, 10]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset16) |
| .add_link(ids[0], ids[3], OffsetLen::Offset16) |
| .add_link(ids[3], ids[1], OffsetLen::Offset16) |
| .build(); |
| |
| graph.sort_kahn(); |
| // 3 links 1, so 1 must be last |
| assert_eq!(&graph.order, &[ids[0], ids[2], ids[3], ids[1]]); |
| } |
| |
| #[test] |
| fn shortest_basic() { |
| let ids = make_ids::<4>(); |
| let sizes = [10, 10, 20, 10]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset16) |
| .add_link(ids[0], ids[3], OffsetLen::Offset16) |
| .build(); |
| |
| graph.sort_shortest_distance(); |
| // but 2 is larger than 3, so should be ordered after |
| assert_eq!(&graph.order, &[ids[0], ids[1], ids[3], ids[2]]); |
| } |
| |
| #[test] |
| fn overflow_basic() { |
| let ids = make_ids::<3>(); |
| let sizes = [10, u16::MAX as usize - 5, 100]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset16) |
| .add_link(ids[1], ids[2], OffsetLen::Offset16) |
| .build(); |
| graph.sort_kahn(); |
| assert_eq!(graph.find_overflows().len(), 1); |
| assert_eq!(graph.find_overflows()[0].parent, ids[0]); |
| assert_eq!(graph.find_overflows()[0].child, ids[2]); |
| } |
| |
| #[test] |
| fn duplicate_subgraph() { |
| let _ = env_logger::builder().is_test(true).try_init(); |
| let ids = make_ids::<10>(); |
| let sizes = [10; 10]; |
| |
| // root has two children, one 16 and one 32-bit offset. |
| // those subgraphs share three nodes, which must be deduped. |
| |
| // |
| // before after |
| // 0 0 |
| // / ⑊ ┌───┘⑊ |
| // 1 2 ---+ 1 2 ---+ |
| // |\ / \ | / \ / \ | |
| // | 3 4 5 9 3 3' 4 5 |
| // | \ / \ | \ / \ |
| // | 6 7 6 6' 7 |
| // | | | |
| // | 8──┘ 8──┘ |
| // | │ / |
| // 9 ───┘ 9' |
| |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[1], ids[3], OffsetLen::Offset16) |
| .add_link(ids[1], ids[9], OffsetLen::Offset16) |
| .add_link(ids[2], ids[3], OffsetLen::Offset16) |
| .add_link(ids[2], ids[4], OffsetLen::Offset16) |
| .add_link(ids[2], ids[5], OffsetLen::Offset16) |
| .add_link(ids[3], ids[6], OffsetLen::Offset16) |
| .add_link(ids[4], ids[6], OffsetLen::Offset16) |
| .add_link(ids[4], ids[7], OffsetLen::Offset16) |
| .add_link(ids[7], ids[8], OffsetLen::Offset16) |
| .add_link(ids[8], ids[9], OffsetLen::Offset16) |
| .build(); |
| |
| assert_eq!(graph.nodes.len(), 10); |
| let one = graph.find_descendents(ids[1]); |
| let two = graph.find_descendents(ids[2]); |
| assert_eq!(one.intersection(&two).count(), 3); |
| |
| graph.assign_spaces_hb(); |
| |
| // 3, 6, and 9 should be duplicated |
| assert_eq!(graph.nodes.len(), 13); |
| let one = graph.find_descendents(ids[1]); |
| let two = graph.find_descendents(ids[2]); |
| assert_eq!(one.intersection(&two).count(), 0); |
| |
| for id in &one { |
| assert!(!graph.nodes.get(id).unwrap().space.is_custom()); |
| } |
| |
| for id in &two { |
| assert!(graph.nodes.get(id).unwrap().space.is_custom()); |
| } |
| } |
| |
| #[test] |
| fn split_overflowing_spaces() { |
| // this attempts to show a simplified version of a gsub table with extension |
| // subtables, before any isolation/deduplication has happened. |
| // |
| // before after |
| // 0 (GSUB) 0 |
| // | | |
| // 1 (lookup List) 1 |
| // | | |
| // 2 (Lookup) 2 |
| // / \ / \ |
| // ╔═3 4═╗ (ext subtables) ╔═3 4═╗ |
| // ║ ║ ║ ║ (long offsets) |
| // 5─┐ ┌─6 (subtables) 5 6 |
| // │ └─8─┘ │ / \ / \ |
| // │ │ (cov tables) 7' 8' 7 8 |
| // └───7───┘ |
| // |
| |
| let _ = env_logger::builder().is_test(true).try_init(); |
| let ids = make_ids::<9>(); |
| // make the coverage tables big enough that overflow is unavoidable |
| let sizes = [10, 4, 12, 8, 8, 14, 14, 65520, 65520]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[1], ids[2], OffsetLen::Offset16) |
| .add_link(ids[2], ids[3], OffsetLen::Offset16) |
| .add_link(ids[2], ids[4], OffsetLen::Offset16) |
| .add_link(ids[3], ids[5], OffsetLen::Offset32) |
| .add_link(ids[4], ids[6], OffsetLen::Offset32) |
| .add_link(ids[5], ids[7], OffsetLen::Offset16) |
| .add_link(ids[5], ids[8], OffsetLen::Offset16) |
| .add_link(ids[6], ids[7], OffsetLen::Offset16) |
| .add_link(ids[6], ids[8], OffsetLen::Offset16) |
| .build(); |
| graph.sort_shortest_distance(); |
| |
| assert!(graph.has_overflows()); |
| assert_eq!(graph.nodes.len(), 9); |
| |
| graph.assign_spaces_hb(); |
| graph.sort_shortest_distance(); |
| |
| // now spaces are assigned, but not isolated |
| assert_eq!(graph.nodes[&ids[5]].space, graph.nodes[&ids[6]].space); |
| assert_eq!(graph.nodes.len(), 9); |
| |
| // now isolate space that overflows |
| let overflows = graph.find_overflows(); |
| graph.try_isolating_subgraphs(&overflows); |
| graph.sort_shortest_distance(); |
| |
| assert_eq!(graph.nodes.len(), 11); |
| assert!(graph.find_overflows().is_empty()); |
| // ensure we are correctly update the roots_per_space thing |
| assert_eq!(graph.num_roots_per_space[&graph.nodes[&ids[6]].space], 1); |
| assert_eq!(graph.num_roots_per_space[&graph.nodes[&ids[5]].space], 1); |
| } |
| |
| #[test] |
| fn all_roads_lead_to_overflow() { |
| // this is a regression test for a bug we had where we would fail |
| // to correctly duplicate shared subgraphs when there were |
| // multiple links between two objects, which caused us to overcount |
| // the 'incoming edges in subgraph'. |
| |
| let _ = env_logger::builder().is_test(true).try_init(); |
| |
| let ids = make_ids::<9>(); |
| let sizes = [10, 10, 10, 10, 10, 65524, 65524, 10, 24]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset32) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[0], ids[3], OffsetLen::Offset32) |
| .add_link(ids[0], ids[4], OffsetLen::Offset32) |
| .add_link(ids[1], ids[5], OffsetLen::Offset16) |
| .add_link(ids[1], ids[5], OffsetLen::Offset16) |
| .add_link(ids[2], ids[6], OffsetLen::Offset16) |
| .add_link(ids[3], ids[7], OffsetLen::Offset16) |
| .add_link(ids[5], ids[8], OffsetLen::Offset16) |
| .add_link(ids[5], ids[8], OffsetLen::Offset16) |
| .add_link(ids[6], ids[8], OffsetLen::Offset16) |
| .add_link(ids[7], ids[8], OffsetLen::Offset16) |
| .build(); |
| |
| graph.assign_spaces_hb(); |
| graph.sort_shortest_distance(); |
| let overflows = graph.find_overflows(); |
| assert!(!overflows.is_empty()); |
| graph.try_isolating_subgraphs(&overflows); |
| graph.sort_shortest_distance(); |
| let overflows = graph.find_overflows(); |
| assert!(!overflows.is_empty()); |
| assert!(graph.try_isolating_subgraphs(&overflows)); |
| graph.sort_shortest_distance(); |
| assert!(!graph.has_overflows()); |
| } |
| |
| #[test] |
| fn two_roots_one_space() { |
| // If a subgraph is reachable from multiple long offsets, they are all |
| // initially placed in the same space. |
| // |
| // ┌──0═══╗ ┌──0═══╗ |
| // │ ║ ║ │ ║ ║ |
| // │ ║ ║ │ ║ ║ |
| // 1 2 3 1 2 3 |
| // │ \ / │ \ / |
| // └────4 4 4' |
| // │ │ │ |
| // 5 5 5' |
| |
| let ids = make_ids::<6>(); |
| let sizes = [10; 6]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[0], ids[3], OffsetLen::Offset32) |
| .add_link(ids[1], ids[4], OffsetLen::Offset16) |
| .add_link(ids[2], ids[4], OffsetLen::Offset16) |
| .add_link(ids[3], ids[4], OffsetLen::Offset16) |
| .add_link(ids[4], ids[5], OffsetLen::Offset16) |
| .build(); |
| |
| assert_eq!(graph.nodes.len(), 6); |
| graph.assign_spaces_hb(); |
| assert_eq!(graph.nodes.len(), 8); |
| let one = graph.find_descendents(ids[1]); |
| assert!(one.iter().all(|id| !graph.nodes[id].space.is_custom())); |
| |
| let two = graph.find_descendents(ids[2]); |
| let three = graph.find_descendents(ids[3]); |
| assert_eq!(two.intersection(&three).count(), 2); |
| assert_eq!(two.union(&three).count(), 4); |
| |
| assert_eq!( |
| two.union(&three) |
| .map(|id| graph.nodes[id].space) |
| .collect::<HashSet<_>>() |
| .len(), |
| 1 |
| ); |
| } |
| |
| #[test] |
| fn duplicate_shared_root_subgraph() { |
| // if a node is linked from both 16 & 32-bit space, and has no parents |
| // in 32 bit space, it should always still be deduped. |
| // |
| // before after |
| // 0 0 |
| // / ⑊ / ⑊ |
| // 1 ⑊ 1 2 |
| // └───╴2 │ |
| // 2' |
| |
| let ids = make_ids::<3>(); |
| let sizes = [10; 3]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[1], ids[2], OffsetLen::Offset16) |
| .build(); |
| graph.assign_spaces_hb(); |
| assert_eq!(graph.nodes.len(), 4); |
| } |
| |
| #[test] |
| fn assign_space_even_without_any_duplication() { |
| // the subgraph of the long offset (0->2) is already isolated, and |
| // so requires no duplication; but we should still correctly assign a |
| // space to the children. |
| // |
| // 0 |
| // / ⑊ |
| // 1 2 |
| // / |
| // 3 |
| |
| let ids = make_ids::<4>(); |
| let sizes = [10; 4]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset16) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[2], ids[3], OffsetLen::Offset16) |
| .build(); |
| graph.assign_spaces_hb(); |
| let two = graph.find_descendents(ids[2]); |
| assert!(two.iter().all(|id| graph.nodes[id].space.is_custom())); |
| } |
| |
| #[test] |
| fn sort_respects_spaces() { |
| let ids = make_ids::<4>(); |
| let sizes = [10; 4]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset32) |
| .add_link(ids[0], ids[2], OffsetLen::Offset32) |
| .add_link(ids[0], ids[3], OffsetLen::Offset16) |
| .build(); |
| graph.sort_shortest_distance(); |
| assert_eq!(&graph.order, &[ids[0], ids[3], ids[1], ids[2]]); |
| } |
| |
| #[test] |
| fn assign_32bit_spaces_if_needed() { |
| let ids = make_ids::<3>(); |
| let sizes = [10, u16::MAX as usize, 10]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset32) |
| .add_link(ids[0], ids[2], OffsetLen::Offset16) |
| .add_link(ids[1], ids[2], OffsetLen::Offset16) |
| .build(); |
| graph.basic_sort(); |
| // this will overflow unless the 32-bit offset is put last. |
| assert!(graph.has_overflows()); |
| graph.pack_objects(); |
| assert!(!graph.has_overflows()); |
| } |
| |
| /// Construct a real gsub table that cannot be packed unless we use extension |
| /// subtables |
| #[test] |
| fn pack_real_gsub_table_with_extension_promotion() { |
| use crate::tables::{gsub, layout}; |
| |
| // trial and error: a number that just triggers overflow. |
| const NUM_SUBTABLES: usize = 3279; |
| |
| // make an rsub rule for each glyph. |
| let rsub_rules = (0u16..NUM_SUBTABLES as u16) |
| .map(|id| { |
| // Each rule will use unique coverage tables, so nothing is shared. |
| let coverage = std::iter::once(GlyphId16::new(id)).collect(); |
| let backtrack = [id + 1, id + 3].into_iter().map(GlyphId16::new).collect(); |
| gsub::ReverseChainSingleSubstFormat1::new( |
| coverage, |
| vec![backtrack], |
| vec![], |
| vec![GlyphId16::new(id + 1)], |
| ) |
| }) |
| .collect(); |
| |
| let list = layout::LookupList::<gsub::SubstitutionLookup>::new(vec![ |
| gsub::SubstitutionLookup::Reverse(layout::Lookup::new( |
| layout::LookupFlag::empty(), |
| rsub_rules, |
| )), |
| ]); |
| let table = gsub::Gsub::new(Default::default(), Default::default(), list); |
| |
| let mut graph = TableWriter::make_graph(&table); |
| assert!( |
| !graph.basic_sort(), |
| "simple sorting should not resolve this graph" |
| ); |
| |
| const BASE_LEN: usize = 10 // GPOS header len |
| + 2 // scriptlist table + featurelist (both empty, get deduped) |
| + 4 // lookup list, one offset |
| + 6; // lookup table (no offsets) |
| const RSUB_LEN: usize = 16 // base table len |
| + 6 // one-glyph coverage table |
| + 8; // two-glyph backtrack coverage table |
| |
| const EXTENSION_LEN: usize = 8; |
| |
| assert_eq!(graph.debug_len(), BASE_LEN + NUM_SUBTABLES * RSUB_LEN); |
| assert!(graph.pack_objects()); |
| assert_eq!( |
| graph.debug_len(), |
| BASE_LEN + NUM_SUBTABLES * RSUB_LEN + NUM_SUBTABLES * EXTENSION_LEN |
| ); |
| |
| const EXPECTED_N_TABLES: usize = 5 // header, script/feature/lookup lists, lookup |
| - 1 // because script/feature are both empty, thus identical |
| + NUM_SUBTABLES * 3 // subtable + coverage + backtrack |
| + NUM_SUBTABLES; // extension table for each subtable |
| assert_eq!(graph.order.len(), EXPECTED_N_TABLES); |
| } |
| |
| #[test] |
| fn pack_real_gpos_table_with_extension_promotion() { |
| use crate::tables::{gpos, layout}; |
| |
| let _ = env_logger::builder().is_test(true).try_init(); |
| |
| fn make_big_pair_pos(glyph_range: Range<u16>) -> gpos::PositionLookup { |
| let coverage = glyph_range.clone().map(GlyphId16::new).collect(); |
| let pair_sets = glyph_range |
| .map(|id| { |
| let value_rec = gpos::ValueRecord::new().with_x_advance(id as _); |
| gpos::PairSet::new( |
| (id..id + 165) |
| .map(|id2| { |
| gpos::PairValueRecord::new( |
| GlyphId16::new(id2), |
| value_rec.clone(), |
| gpos::ValueRecord::default(), |
| ) |
| }) |
| .collect(), |
| ) |
| }) |
| .collect::<Vec<_>>(); |
| gpos::PositionLookup::Pair(layout::Lookup::new( |
| layout::LookupFlag::empty(), |
| vec![gpos::PairPos::format_1(coverage, pair_sets)], |
| )) |
| } |
| |
| // this is a shallow graph with large nodes, which makes it easier |
| // to visualize with graphviz. |
| let pp1 = make_big_pair_pos(1..20); |
| let pp2 = make_big_pair_pos(100..120); |
| let pp3 = make_big_pair_pos(200..221); |
| let pp4 = make_big_pair_pos(400..422); |
| let pp5 = make_big_pair_pos(500..523); |
| let pp6 = make_big_pair_pos(600..624); |
| let table = gpos::Gpos::new( |
| Default::default(), |
| Default::default(), |
| layout::LookupList::new(vec![pp1, pp2, pp3, pp4, pp5, pp6]), |
| ); |
| |
| // this constructs a graph where there are overflows in a single pairpos |
| // subtable. |
| let mut graph = TableWriter::make_graph(&table); |
| assert!( |
| !graph.basic_sort(), |
| "simple sorting should not resolve this graph", |
| ); |
| |
| // uncomment these two lines if you want to visualize the graph: |
| |
| //graph.write_graph_viz("promote_gpos_before.dot"); |
| |
| let n_tables_before = graph.order.len(); |
| assert!(graph.pack_objects()); |
| |
| //graph.write_graph_viz("promote_gpos_after.dot"); |
| |
| // we should have resolved this overflow by promoting a single lookup |
| // to be an extension, but our logic for determining when to promote |
| // is not quite perfect, so it promotes an extra. |
| // |
| // if our impl changes and this is failing because we're only promoting |
| // a single extension, then that's great |
| assert_eq!(n_tables_before + 2, graph.order.len()); |
| } |
| |
| #[test] |
| fn unpackable_graph_should_fail() { |
| let _ = env_logger::builder().is_test(true).try_init(); |
| // specifically, it should not run forever. |
| let ids = make_ids::<4>(); |
| let sizes = [10, 10, 66000, 66000]; |
| let mut graph = TestGraphBuilder::new(ids, sizes) |
| .add_link(ids[0], ids[1], OffsetLen::Offset32) |
| .add_link(ids[1], ids[2], OffsetLen::Offset16) |
| .add_link(ids[1], ids[3], OffsetLen::Offset16) |
| .build(); |
| |
| assert!(!graph.pack_objects()); |
| } |
| } |
