More efficient guard storage

3 files changed, 124 insertions, 12 deletions

diff --git a/crates/typst/src/foundations/content.rs b/crates/typst/src/foundations/content.rs
index 16ab0c04..8a734635 100644
--- a/crates/typst/src/foundations/content.rs
+++ b/crates/typst/src/foundations/content.rs
@@ -22,7 +22,7 @@ use crate::layout::{AlignElem, Alignment, Axes, Length, MoveElem, PadElem, Rel,
 use crate::model::{Destination, EmphElem, StrongElem};
 use crate::syntax::Span;
 use crate::text::UnderlineElem;
-use crate::util::fat;
+use crate::util::{fat, BitSet};
 
 /// A piece of document content.
 ///
@@ -71,17 +71,25 @@ use crate::util::fat;
 #[derive(Clone, Hash)]
 #[allow(clippy::derived_hash_with_manual_eq)]
 pub struct Content {
+    /// The partially element-dependant inner data.
     inner: Arc<Inner<dyn Bounds>>,
+    /// The element's source code location.
     span: Span,
 }
 
 /// The inner representation behind the `Arc`.
 #[derive(Hash)]
 struct Inner<T: ?Sized> {
+    /// An optional label attached to the element.
     label: Option<Label>,
+    /// The element's location which identifies it in the layouted output.
     location: Option<Location>,
-    prepared: bool,
-    guards: Vec<Guard>,
+    /// Manages the element during realization.
+    /// - If bit 0 is set, the element is prepared.
+    /// - If bit n is set, the element is guarded against the n-th show rule
+    ///   recipe from the top of the style chain (counting from 1).
+    lifecycle: BitSet,
+    /// The element's raw data.
     elem: T,
 }
 
@@ -92,8 +100,7 @@ impl Content {
             inner: Arc::new(Inner {
                 label: None,
                 location: None,
-                prepared: false,
-                guards: vec![],
+                lifecycle: BitSet::new(),
                 elem,
             }),
             span: Span::detached(),
@@ -141,13 +148,13 @@ impl Content {
 
     /// Disable a show rule recipe.
     pub fn guarded(mut self, guard: Guard) -> Self {
-        self.make_mut().guards.push(guard);
+        self.make_mut().lifecycle.insert(guard.0);
         self
     }
 
     /// Whether the content needs to be realized specially.
     pub fn needs_preparation(&self) -> bool {
-        !self.inner.prepared
+        !self.is_prepared()
             && (self.can::<dyn Locatable>()
                 || self.can::<dyn Synthesize>()
                 || self.can::<dyn Finalize>()
@@ -156,17 +163,17 @@ impl Content {
 
     /// Check whether a show rule recipe is disabled.
     pub fn is_guarded(&self, guard: Guard) -> bool {
-        self.inner.guards.contains(&guard)
+        self.inner.lifecycle.contains(guard.0)
     }
 
     /// Whether this content has already been prepared.
     pub fn is_prepared(&self) -> bool {
-        self.inner.prepared
+        self.inner.lifecycle.contains(0)
     }
 
     /// Mark this content as prepared.
     pub fn mark_prepared(&mut self) {
-        self.make_mut().prepared = true;
+        self.make_mut().lifecycle.insert(0);
     }
 
     /// Get a field by ID.
@@ -716,8 +723,7 @@ impl<T: NativeElement> Bounds for T {
             inner: Arc::new(Inner {
                 label: inner.label,
                 location: inner.location,
-                prepared: inner.prepared,
-                guards: inner.guards.clone(),
+                lifecycle: inner.lifecycle.clone(),
                 elem: self.clone(),
             }),
             span,
diff --git a/crates/typst/src/util/bitset.rs b/crates/typst/src/util/bitset.rs
new file mode 100644
index 00000000..cbac7a1e
--- /dev/null
+++ b/crates/typst/src/util/bitset.rs
@@ -0,0 +1,104 @@
+use std::fmt::{self, Debug, Formatter};
+
+/// Efficiently stores a set of numbers which are expected to be very small
+/// (< 32/64 depending on the architecture).
+///
+/// Inserting a very small value is very cheap while inserting a large one may
+/// be very expensive.
+#[derive(Clone, PartialEq, Hash)]
+pub struct BitSet {
+    /// Used to store values < BITS.
+    low: usize,
+    /// Used to store values > BITS. We have the extra `Box` to keep the memory
+    /// size of the `BitSet` down.
+    #[allow(clippy::box_collection)]
+    hi: Option<Box<Vec<usize>>>,
+}
+
+/// The number of bits per chunk.
+const BITS: usize = usize::BITS as usize;
+
+impl BitSet {
+    /// Creates a new empty bit set.
+    pub fn new() -> Self {
+        Self { low: 0, hi: None }
+    }
+
+    /// Inserts a number into the set.
+    pub fn insert(&mut self, value: usize) {
+        if value < BITS {
+            self.low |= 1 << value;
+        } else {
+            let chunk = value / BITS - 1;
+            let within = value % BITS;
+            let vec = self.hi.get_or_insert_with(Default::default);
+            if chunk >= vec.len() {
+                vec.resize(chunk + 1, 0);
+            }
+            vec[chunk] |= 1 << within;
+        }
+    }
+
+    /// Whether a number is present in the set.
+    pub fn contains(&self, value: usize) -> bool {
+        if value < BITS {
+            (self.low & (1 << value)) != 0
+        } else {
+            let Some(hi) = &self.hi else { return false };
+            let chunk = value / BITS - 1;
+            let within = value % BITS;
+            let Some(bits) = hi.get(chunk) else { return false };
+            (bits & (1 << within)) != 0
+        }
+    }
+}
+
+impl Default for BitSet {
+    fn default() -> Self {
+        Self::new()
+    }
+}
+
+impl Debug for BitSet {
+    fn fmt(&self, f: &mut Formatter) -> fmt::Result {
+        let mut list = f.debug_list();
+        let chunks = 1 + self.hi.as_ref().map_or(0, |v| v.len());
+        for v in 0..chunks * BITS {
+            if self.contains(v) {
+                list.entry(&v);
+            }
+        }
+        list.finish()
+    }
+}
+
+#[cfg(test)]
+mod tests {
+    use super::*;
+
+    #[test]
+    fn test_bitset() {
+        let mut set = BitSet::new();
+        assert!(!set.contains(0));
+        assert!(!set.contains(5));
+        set.insert(0);
+        set.insert(1);
+        set.insert(5);
+        set.insert(64);
+        set.insert(105);
+        set.insert(208);
+        assert!(set.contains(0));
+        assert!(set.contains(1));
+        assert!(!set.contains(2));
+        assert!(set.contains(5));
+        assert!(!set.contains(63));
+        assert!(set.contains(64));
+        assert!(!set.contains(65));
+        assert!(!set.contains(104));
+        assert!(set.contains(105));
+        assert!(!set.contains(106));
+        assert!(set.contains(208));
+        assert!(!set.contains(209));
+        assert_eq!(format!("{set:?}"), "[0, 1, 5, 64, 105, 208]");
+    }
+}
diff --git a/crates/typst/src/util/mod.rs b/crates/typst/src/util/mod.rs
index a57c6f08..05ff6e11 100644
--- a/crates/typst/src/util/mod.rs
+++ b/crates/typst/src/util/mod.rs
@@ -4,10 +4,12 @@ pub mod fat;
 
 #[macro_use]
 mod macros;
+mod bitset;
 mod deferred;
 mod pico;
 mod scalar;
 
+pub use self::bitset::BitSet;
 pub use self::deferred::Deferred;
 pub use self::pico::PicoStr;
 pub use self::scalar::Scalar;