Bring back `StyleVec` (#4323)

9 files changed, 162 insertions, 112 deletions

diff --git a/crates/typst/src/foundations/styles.rs b/crates/typst/src/foundations/styles.rs
index 7a75c5d5..42be8922 100644
--- a/crates/typst/src/foundations/styles.rs
+++ b/crates/typst/src/foundations/styles.rs
@@ -72,8 +72,8 @@ pub struct Styles(EcoVec<LazyHash<Style>>);
 
 impl Styles {
     /// Create a new, empty style list.
-    pub fn new() -> Self {
-        Self::default()
+    pub const fn new() -> Self {
+        Self(EcoVec::new())
     }
 
     /// Whether this contains no styles.
diff --git a/crates/typst/src/layout/flow.rs b/crates/typst/src/layout/flow.rs
index 5ae28cde..8ae68183 100644
--- a/crates/typst/src/layout/flow.rs
+++ b/crates/typst/src/layout/flow.rs
@@ -9,7 +9,7 @@ use std::fmt::{self, Debug, Formatter};
 use crate::diag::{bail, SourceResult};
 use crate::engine::Engine;
 use crate::foundations::{
-    elem, Content, NativeElement, Packed, Resolve, Smart, StyleChain, StyledElem,
+    elem, Args, Construct, Content, NativeElement, Packed, Resolve, Smart, StyleChain,
 };
 use crate::introspection::TagElem;
 use crate::layout::{
@@ -17,17 +17,25 @@ use crate::layout::{
     Fragment, Frame, FrameItem, PlaceElem, Point, Regions, Rel, Size, Spacing, VElem,
 };
 use crate::model::{FootnoteElem, FootnoteEntry, ParElem};
+use crate::realize::StyleVec;
 use crate::utils::Numeric;
 
 /// Arranges spacing, paragraphs and block-level elements into a flow.
 ///
 /// This element is responsible for layouting both the top-level content flow
 /// and the contents of boxes.
-#[elem(Debug)]
+#[elem(Debug, Construct)]
 pub struct FlowElem {
     /// The children that will be arranged into a flow.
+    #[internal]
     #[variadic]
-    pub children: Vec<Content>,
+    pub children: StyleVec,
+}
+
+impl Construct for FlowElem {
+    fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> {
+        bail!(args.span, "cannot be constructed manually");
+    }
 }
 
 impl Packed<FlowElem> {
@@ -54,23 +62,12 @@ impl Packed<FlowElem> {
         // through the block & pad and reach the innermost flow, so that things
         // are properly bottom-aligned.
         let mut alone = false;
-        if let [child] = self.children().as_slice() {
-            alone = child
-                .to_packed::<StyledElem>()
-                .map_or(child, |styled| &styled.child)
-                .is::<BlockElem>();
+        if let [child] = self.children().elements() {
+            alone = child.is::<BlockElem>();
         }
 
-        let outer = styles;
-
         let mut layouter = FlowLayouter::new(regions, styles, alone);
-        for mut child in self.children().iter() {
-            let mut styles = styles;
-            if let Some(styled) = child.to_packed::<StyledElem>() {
-                child = &styled.child;
-                styles = outer.chain(&styled.styles);
-            }
-
+        for (child, styles) in self.children().chain(&styles) {
             if let Some(elem) = child.to_packed::<TagElem>() {
                 layouter.layout_tag(elem);
             } else if child.is::<FlushElem>() {
@@ -100,7 +97,7 @@ impl Packed<FlowElem> {
 impl Debug for FlowElem {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
         write!(f, "Flow ")?;
-        f.debug_list().entries(&self.children).finish()
+        self.children.fmt(f)
     }
 }
 
diff --git a/crates/typst/src/layout/inline/mod.rs b/crates/typst/src/layout/inline/mod.rs
index 5d4dd011..4fffa7eb 100644
--- a/crates/typst/src/layout/inline/mod.rs
+++ b/crates/typst/src/layout/inline/mod.rs
@@ -13,13 +13,14 @@ use self::shaping::{
 use crate::diag::{bail, SourceResult};
 use crate::engine::{Engine, Route};
 use crate::eval::Tracer;
-use crate::foundations::{Content, Packed, Resolve, Smart, StyleChain, StyledElem};
+use crate::foundations::{Packed, Resolve, Smart, StyleChain};
 use crate::introspection::{Introspector, Locator, TagElem};
 use crate::layout::{
     Abs, AlignElem, BoxElem, Dir, Em, FixedAlignment, Fr, Fragment, Frame, FrameItem,
     HElem, InlineElem, InlineItem, Point, Size, Sizing, Spacing,
 };
 use crate::model::{Linebreaks, ParElem};
+use crate::realize::StyleVec;
 use crate::syntax::Span;
 use crate::text::{
     Costs, Lang, LinebreakElem, SmartQuoteElem, SmartQuoter, SmartQuotes, SpaceElem,
@@ -30,7 +31,7 @@ use crate::World;
 
 /// Layouts content inline.
 pub(crate) fn layout_inline(
-    children: &[Content],
+    children: &StyleVec,
     engine: &mut Engine,
     styles: StyleChain,
     consecutive: bool,
@@ -40,7 +41,7 @@ pub(crate) fn layout_inline(
     #[comemo::memoize]
     #[allow(clippy::too_many_arguments)]
     fn cached(
-        children: &[Content],
+        children: &StyleVec,
         world: Tracked<dyn World + '_>,
         introspector: Tracked<Introspector>,
         route: Tracked<Route>,
@@ -428,14 +429,14 @@ impl<'a> Line<'a> {
 /// Collect all text of the paragraph into one string and layout equations. This
 /// also performs string-level preprocessing like case transformations.
 fn collect<'a>(
-    children: &'a [Content],
+    children: &'a StyleVec,
     engine: &mut Engine<'_>,
     styles: &'a StyleChain<'a>,
     region: Size,
     consecutive: bool,
 ) -> SourceResult<(String, Vec<Segment<'a>>, SpanMapper)> {
     let mut collector = Collector::new(2 + children.len());
-    let mut iter = children.iter().peekable();
+    let mut iter = children.chain(styles).peekable();
 
     let first_line_indent = ParElem::first_line_indent_in(*styles);
     if !first_line_indent.is_zero()
@@ -455,14 +456,7 @@ fn collect<'a>(
 
     let outer_dir = TextElem::dir_in(*styles);
 
-    while let Some(mut child) = iter.next() {
-        let outer = styles;
-        let mut styles = *styles;
-        if let Some(styled) = child.to_packed::<StyledElem>() {
-            child = &styled.child;
-            styles = outer.chain(&styled.styles);
-        }
-
+    while let Some((child, styles)) = iter.next() {
         let prev_len = collector.full.len();
 
         if child.is::<SpaceElem>() {
@@ -515,12 +509,7 @@ fn collect<'a>(
                     TextElem::region_in(styles),
                     elem.alternative(styles),
                 );
-                let peeked = iter.peek().and_then(|&child| {
-                    let child = if let Some(styled) = child.to_packed::<StyledElem>() {
-                        &styled.child
-                    } else {
-                        child
-                    };
+                let peeked = iter.peek().and_then(|(child, _)| {
                     if let Some(elem) = child.to_packed::<TextElem>() {
                         elem.text().chars().next()
                     } else if child.is::<SmartQuoteElem>() {
@@ -642,7 +631,7 @@ impl<'a> Collector<'a> {
 /// Prepare paragraph layout by shaping the whole paragraph.
 fn prepare<'a>(
     engine: &mut Engine,
-    children: &'a [Content],
+    children: &'a StyleVec,
     text: &'a str,
     segments: Vec<Segment<'a>>,
     spans: SpanMapper,
@@ -682,9 +671,9 @@ fn prepare<'a>(
         bidi,
         items,
         spans,
-        hyphenate: shared_get(styles, children, TextElem::hyphenate_in),
+        hyphenate: children.shared_get(styles, TextElem::hyphenate_in),
         costs: TextElem::costs_in(styles),
-        lang: shared_get(styles, children, TextElem::lang_in),
+        lang: children.shared_get(styles, TextElem::lang_in),
         align: AlignElem::alignment_in(styles).resolve(styles).x,
         justify: ParElem::justify_in(styles),
         hang: ParElem::hanging_indent_in(styles),
@@ -815,21 +804,6 @@ fn is_compatible(a: Script, b: Script) -> bool {
     is_generic_script(a) || is_generic_script(b) || a == b
 }
 
-/// Get a style property, but only if it is the same for all children of the
-/// paragraph.
-fn shared_get<T: PartialEq>(
-    styles: StyleChain<'_>,
-    children: &[Content],
-    getter: fn(StyleChain) -> T,
-) -> Option<T> {
-    let value = getter(styles);
-    children
-        .iter()
-        .filter_map(|child| child.to_packed::<StyledElem>())
-        .all(|styled| getter(styles.chain(&styled.styles)) == value)
-        .then_some(value)
-}
-
 /// Find suitable linebreaks.
 fn linebreak<'a>(engine: &Engine, p: &'a Preparation<'a>, width: Abs) -> Vec<Line<'a>> {
     let linebreaks = p.linebreaks.unwrap_or_else(|| {
diff --git a/crates/typst/src/math/ctx.rs b/crates/typst/src/math/ctx.rs
index 88a0664c..b5ed6682 100644
--- a/crates/typst/src/math/ctx.rs
+++ b/crates/typst/src/math/ctx.rs
@@ -1,6 +1,6 @@
 use std::f64::consts::SQRT_2;
 
-use ecow::EcoString;
+use ecow::{eco_vec, EcoString};
 use rustybuzz::Feature;
 use ttf_parser::gsub::{AlternateSubstitution, SingleSubstitution, SubstitutionSubtable};
 use ttf_parser::math::MathValue;
@@ -18,6 +18,7 @@ use crate::math::{
     LayoutMath, MathFragment, MathRun, MathSize, THICK,
 };
 use crate::model::ParElem;
+use crate::realize::StyleVec;
 use crate::syntax::{is_newline, Span};
 use crate::text::{
     features, BottomEdge, BottomEdgeMetric, Font, TextElem, TextSize, TopEdge,
@@ -286,7 +287,7 @@ impl<'a, 'b, 'v> MathContext<'a, 'b, 'v> {
         // to extend as far as needed.
         let spaced = text.graphemes(true).nth(1).is_some();
         let text = TextElem::packed(text).spanned(span);
-        let par = ParElem::new(vec![text]);
+        let par = ParElem::new(StyleVec::wrap(eco_vec![text]));
         let frame = Packed::new(par)
             .spanned(span)
             .layout(self.engine, styles, false, Size::splat(Abs::inf()), false)?
diff --git a/crates/typst/src/math/mod.rs b/crates/typst/src/math/mod.rs
index 305f9188..a97f56dc 100644
--- a/crates/typst/src/math/mod.rs
+++ b/crates/typst/src/math/mod.rs
@@ -241,7 +241,7 @@ impl LayoutMath for Content {
             self.sequence_recursive_for_each(&mut |child: &Content| {
                 bb.push(child, StyleChain::default());
             });
-            for child in bb.finish::<Content>().0 {
+            for (child, _) in bb.finish().0.chain(&styles) {
                 child.layout_math(ctx, styles)?;
             }
             return Ok(());
diff --git a/crates/typst/src/model/document.rs b/crates/typst/src/model/document.rs
index e613d07f..ebe21505 100644
--- a/crates/typst/src/model/document.rs
+++ b/crates/typst/src/model/document.rs
@@ -4,10 +4,11 @@ use crate::diag::{bail, SourceResult, StrResult};
 use crate::engine::Engine;
 use crate::foundations::{
     cast, elem, Args, Array, Construct, Content, Datetime, Packed, Smart, StyleChain,
-    StyledElem, Value,
+    Value,
 };
 use crate::introspection::{Introspector, ManualPageCounter};
 use crate::layout::{Page, PageElem};
+use crate::realize::StyleVec;
 
 /// The root element of a document and its metadata.
 ///
@@ -60,7 +61,7 @@ pub struct DocumentElem {
     /// The page runs.
     #[internal]
     #[variadic]
-    pub children: Vec<Content>,
+    pub children: StyleVec,
 }
 
 impl Construct for DocumentElem {
@@ -81,24 +82,13 @@ impl Packed<DocumentElem> {
         let mut page_counter = ManualPageCounter::new();
 
         let children = self.children();
-        let mut iter = children.iter().peekable();
-
-        while let Some(mut child) = iter.next() {
-            let outer = styles;
-            let mut styles = styles;
-            if let Some(styled) = child.to_packed::<StyledElem>() {
-                child = &styled.child;
-                styles = outer.chain(&styled.styles);
-            }
+        let mut iter = children.chain(&styles).peekable();
 
+        while let Some((child, styles)) = iter.next() {
             if let Some(page) = child.to_packed::<PageElem>() {
-                let extend_to = iter.peek().and_then(|&next| {
-                    *next
-                        .to_packed::<StyledElem>()
-                        .map_or(next, |styled| &styled.child)
-                        .to_packed::<PageElem>()?
-                        .clear_to()?
-                });
+                let extend_to = iter
+                    .peek()
+                    .and_then(|(next, _)| *next.to_packed::<PageElem>()?.clear_to()?);
                 let run = page.layout(engine, styles, &mut page_counter, extend_to)?;
                 pages.extend(run);
             } else {
diff --git a/crates/typst/src/model/par.rs b/crates/typst/src/model/par.rs
index f8a833ac..7615ddba 100644
--- a/crates/typst/src/model/par.rs
+++ b/crates/typst/src/model/par.rs
@@ -7,6 +7,7 @@ use crate::foundations::{
     Unlabellable,
 };
 use crate::layout::{Em, Fragment, Length, Size};
+use crate::realize::StyleVec;
 
 /// Arranges text, spacing and inline-level elements into a paragraph.
 ///
@@ -113,7 +114,7 @@ pub struct ParElem {
     /// The paragraph's children.
     #[internal]
     #[variadic]
-    pub children: Vec<Content>,
+    pub children: StyleVec,
 }
 
 impl Construct for ParElem {
@@ -143,7 +144,7 @@ impl Packed<ParElem> {
         expand: bool,
     ) -> SourceResult<Fragment> {
         crate::layout::layout_inline(
-            self.children(),
+            &self.children,
             engine,
             styles,
             consecutive,
@@ -156,7 +157,7 @@ impl Packed<ParElem> {
 impl Debug for ParElem {
     fn fmt(&self, f: &mut Formatter) -> fmt::Result {
         write!(f, "Par ")?;
-        f.debug_list().entries(&self.children).finish()
+        self.children.fmt(f)
     }
 }
 
diff --git a/crates/typst/src/realize/behaviour.rs b/crates/typst/src/realize/behaviour.rs
index ae44a23e..de6fb8a0 100644
--- a/crates/typst/src/realize/behaviour.rs
+++ b/crates/typst/src/realize/behaviour.rs
@@ -1,5 +1,9 @@
 //! Element interaction.
 
+use std::fmt::{Debug, Formatter};
+
+use ecow::EcoVec;
+
 use crate::foundations::{Content, StyleChain, Styles};
 use crate::syntax::Span;
 
@@ -125,44 +129,39 @@ impl<'a> BehavedBuilder<'a> {
 
     /// Return the built content (possibly styled with local styles) plus a
     /// trunk style chain and a span for the collection.
-    pub fn finish<F: From<Content>>(self) -> (Vec<F>, StyleChain<'a>, Span) {
-        let (output, trunk, span) = self.finish_iter();
-        let output = output.map(|(c, s)| c.clone().styled_with_map(s).into()).collect();
-        (output, trunk, span)
-    }
-
-    /// Return an iterator over the built content and its local styles plus a
-    /// trunk style chain and a span for the collection.
-    pub fn finish_iter(
-        mut self,
-    ) -> (impl Iterator<Item = (&'a Content, Styles)>, StyleChain<'a>, Span) {
+    pub fn finish(mut self) -> (StyleVec, StyleChain<'a>, Span) {
         self.trim_weak();
 
         let span = self.determine_span();
         let (trunk, depth) = self.determine_style_trunk();
 
-        let mut iter = self.buf.into_iter().peekable();
-        let mut reuse = None;
+        let mut elements = EcoVec::with_capacity(self.buf.len());
+        let mut styles = EcoVec::<(Styles, usize)>::new();
+        let mut last: Option<(StyleChain<'a>, usize)> = None;
 
-        // Map the content + style chains to content + suffix maps, reusing
-        // equivalent adjacent suffix maps, if possible.
-        let output = std::iter::from_fn(move || {
-            let (c, s) = iter.next()?;
+        for (element, chain) in self.buf.into_iter() {
+            elements.push(element.clone());
 
-            // Try to reuse a suffix map that the previous element has
-            // stored for us.
-            let suffix = reuse.take().unwrap_or_else(|| s.suffix(depth));
-
-            // Store a suffix map for the next element if it has the same style
-            // chain.
-            if iter.peek().is_some_and(|&(_, s2)| s == s2) {
-                reuse = Some(suffix.clone());
+            if let Some((prev, run)) = &mut last {
+                if chain == *prev {
+                    *run += 1;
+                } else {
+                    styles.push((prev.suffix(depth), *run));
+                    last = Some((chain, 1));
+                }
+            } else {
+                last = Some((chain, 1));
             }
+        }
 
-            Some((c, suffix))
-        });
+        if let Some((last, run)) = last {
+            let skippable = styles.is_empty() && last == trunk;
+            if !skippable {
+                styles.push((last.suffix(depth), run));
+            }
+        }
 
-        (output, trunk, span)
+        (StyleVec { elements, styles }, trunk, span)
     }
 
     /// Trim a possibly remaining weak item.
@@ -228,3 +227,91 @@ impl<'a> Default for BehavedBuilder<'a> {
         Self::new()
     }
 }
+
+/// A sequence of elements with associated styles.
+#[derive(Clone, PartialEq, Hash)]
+pub struct StyleVec {
+    elements: EcoVec<Content>,
+    styles: EcoVec<(Styles, usize)>,
+}
+
+impl StyleVec {
+    /// Create a style vector from an unstyled vector content.
+    pub fn wrap(elements: EcoVec<Content>) -> Self {
+        Self { elements, styles: EcoVec::new() }
+    }
+
+    /// Whether there are no elements.
+    pub fn is_empty(&self) -> bool {
+        self.elements.is_empty()
+    }
+
+    /// The number of elements.
+    pub fn len(&self) -> usize {
+        self.elements.len()
+    }
+
+    /// The raw, unstyled elements.
+    pub fn elements(&self) -> &[Content] {
+        &self.elements
+    }
+
+    /// Get a style property, but only if it is the same for all children of the
+    /// style vector.
+    pub fn shared_get<T: PartialEq>(
+        &self,
+        styles: StyleChain<'_>,
+        getter: fn(StyleChain) -> T,
+    ) -> Option<T> {
+        let value = getter(styles);
+        self.styles
+            .iter()
+            .all(|(local, _)| getter(styles.chain(local)) == value)
+            .then_some(value)
+    }
+
+    /// Iterate over the contained content and style chains.
+    pub fn chain<'a>(
+        &'a self,
+        outer: &'a StyleChain<'_>,
+    ) -> impl Iterator<Item = (&'a Content, StyleChain<'a>)> {
+        self.iter().map(|(element, local)| (element, outer.chain(local)))
+    }
+
+    /// Iterate over pairs of content and styles.
+    pub fn iter(&self) -> impl Iterator<Item = (&Content, &Styles)> {
+        static EMPTY: Styles = Styles::new();
+        self.elements.iter().zip(
+            self.styles
+                .iter()
+                .flat_map(|(local, count)| std::iter::repeat(local).take(*count))
+                .chain(std::iter::repeat(&EMPTY)),
+        )
+    }
+
+    /// Iterate over pairs of content and styles.
+    #[allow(clippy::should_implement_trait)]
+    pub fn into_iter(self) -> impl Iterator<Item = (Content, Styles)> {
+        self.elements.into_iter().zip(
+            self.styles
+                .into_iter()
+                .flat_map(|(local, count)| std::iter::repeat(local).take(count))
+                .chain(std::iter::repeat(Styles::new())),
+        )
+    }
+}
+
+impl Debug for StyleVec {
+    fn fmt(&self, f: &mut Formatter) -> std::fmt::Result {
+        f.debug_list()
+            .entries(self.iter().map(|(element, local)| {
+                typst_utils::debug(|f| {
+                    for style in local.iter() {
+                        writeln!(f, "#{style:?}")?;
+                    }
+                    element.fmt(f)
+                })
+            }))
+            .finish()
+    }
+}
diff --git a/crates/typst/src/realize/mod.rs b/crates/typst/src/realize/mod.rs
index d6b0032c..97b39b4a 100644
--- a/crates/typst/src/realize/mod.rs
+++ b/crates/typst/src/realize/mod.rs
@@ -11,7 +11,7 @@ mod behaviour;
 mod process;
 
 pub use self::arenas::Arenas;
-pub use self::behaviour::{Behave, BehavedBuilder, Behaviour};
+pub use self::behaviour::{Behave, BehavedBuilder, Behaviour, StyleVec};
 pub use self::process::process;
 
 use std::mem;
@@ -504,8 +504,8 @@ impl<'a> ListBuilder<'a> {
     /// Turns this builder into the resulting list, along with
     /// its [style chain][StyleChain].
     fn finish(self) -> (Content, StyleChain<'a>) {
-        let (items, trunk, span) = self.items.finish_iter();
-        let mut items = items.peekable();
+        let (items, trunk, span) = self.items.finish();
+        let mut items = items.into_iter().peekable();
         let (first, _) = items.peek().unwrap();
         let output = if first.is::<ListItem>() {
             ListElem::new(