diff options
23 files changed, 264 insertions, 144 deletions
@@ -1748,6 +1748,12 @@ dependencies = [ ] [[package]] +name = "portable-atomic" +version = "1.6.0" +source = "registry+https://github.com/rust-lang/crates.io-index" +checksum = "7170ef9988bc169ba16dd36a7fa041e5c4cbeb6a35b76d4c03daded371eae7c0" + +[[package]] name = "postcard" version = "1.0.8" source = "registry+https://github.com/rust-lang/crates.io-index" @@ -2578,6 +2584,7 @@ dependencies = [ "once_cell", "palette", "phf", + "portable-atomic", "qcms", "rayon", "regex", @@ -75,6 +75,7 @@ pathdiff = "0.2" pdf-writer = "0.9.2" phf = { version = "0.11", features = ["macros"] } pixglyph = "0.3" +portable-atomic = "1.6" proc-macro2 = "1" pulldown-cmark = "0.9" quote = "1" diff --git a/crates/typst-cli/src/query.rs b/crates/typst-cli/src/query.rs index f2e52666..0b14a893 100644 --- a/crates/typst-cli/src/query.rs +++ b/crates/typst-cli/src/query.rs @@ -78,7 +78,6 @@ fn retrieve( .introspector .query(&selector.0) .into_iter() - .map(|x| x.into_inner()) .collect::<Vec<_>>()) } diff --git a/crates/typst/Cargo.toml b/crates/typst/Cargo.toml index 0f33dbac..8c3ef084 100644 --- a/crates/typst/Cargo.toml +++ b/crates/typst/Cargo.toml @@ -44,6 +44,7 @@ once_cell = { workspace = true } palette = { workspace = true } qcms = { workspace = true } phf = { workspace = true } +portable-atomic = { workspace = true } rayon = { workspace = true } regex = { workspace = true } roxmltree = { workspace = true } diff --git a/crates/typst/src/eval/call.rs b/crates/typst/src/eval/call.rs index 3717903c..26626b1e 100644 --- a/crates/typst/src/eval/call.rs +++ b/crates/typst/src/eval/call.rs @@ -1,4 +1,4 @@ -use comemo::{Prehashed, Tracked, TrackedMut}; +use comemo::{Tracked, TrackedMut}; use ecow::{eco_format, EcoVec}; use crate::diag::{bail, error, At, HintedStrResult, SourceResult, Trace, Tracepoint}; @@ -14,6 +14,7 @@ use crate::symbols::Symbol; use crate::syntax::ast::{self, AstNode}; use crate::syntax::{Spanned, SyntaxNode}; use crate::text::TextElem; +use crate::util::LazyHash; use crate::World; impl Eval for ast::FuncCall<'_> { @@ -260,7 +261,7 @@ impl Eval for ast::Closure<'_> { #[allow(clippy::too_many_arguments)] pub(crate) fn call_closure( func: &Func, - closure: &Prehashed<Closure>, + closure: &LazyHash<Closure>, world: Tracked<dyn World + '_>, introspector: Tracked<Introspector>, route: Tracked<Route>, diff --git a/crates/typst/src/foundations/bytes.rs b/crates/typst/src/foundations/bytes.rs index 3c6fa1fa..605af065 100644 --- a/crates/typst/src/foundations/bytes.rs +++ b/crates/typst/src/foundations/bytes.rs @@ -3,12 +3,12 @@ use std::fmt::{self, Debug, Formatter}; use std::ops::{Add, AddAssign, Deref}; use std::sync::Arc; -use comemo::Prehashed; use ecow::{eco_format, EcoString}; use serde::{Serialize, Serializer}; use crate::diag::{bail, StrResult}; use crate::foundations::{cast, func, scope, ty, Array, Reflect, Repr, Str, Value}; +use crate::util::LazyHash; /// A sequence of bytes. /// @@ -40,12 +40,12 @@ use crate::foundations::{cast, func, scope, ty, Array, Reflect, Repr, Str, Value /// ``` #[ty(scope, cast)] #[derive(Clone, Hash, Eq, PartialEq)] -pub struct Bytes(Arc<Prehashed<Cow<'static, [u8]>>>); +pub struct Bytes(Arc<LazyHash<Cow<'static, [u8]>>>); impl Bytes { /// Create a buffer from a static byte slice. pub fn from_static(slice: &'static [u8]) -> Self { - Self(Arc::new(Prehashed::new(Cow::Borrowed(slice)))) + Self(Arc::new(LazyHash::new(Cow::Borrowed(slice)))) } /// Return `true` if the length is 0. @@ -182,13 +182,13 @@ impl AsRef<[u8]> for Bytes { impl From<&[u8]> for Bytes { fn from(slice: &[u8]) -> Self { - Self(Arc::new(Prehashed::new(slice.to_vec().into()))) + Self(Arc::new(LazyHash::new(slice.to_vec().into()))) } } impl From<Vec<u8>> for Bytes { fn from(vec: Vec<u8>) -> Self { - Self(Arc::new(Prehashed::new(vec.into()))) + Self(Arc::new(LazyHash::new(vec.into()))) } } @@ -208,9 +208,7 @@ impl AddAssign for Bytes { } else if self.is_empty() { *self = rhs; } else if Arc::strong_count(&self.0) == 1 && matches!(**self.0, Cow::Owned(_)) { - Arc::make_mut(&mut self.0).update(|cow| { - cow.to_mut().extend_from_slice(&rhs); - }) + Arc::make_mut(&mut self.0).to_mut().extend_from_slice(&rhs); } else { *self = Self::from([self.as_slice(), rhs.as_slice()].concat()); } diff --git a/crates/typst/src/foundations/cast.rs b/crates/typst/src/foundations/cast.rs index 716eae9d..8e75dc71 100644 --- a/crates/typst/src/foundations/cast.rs +++ b/crates/typst/src/foundations/cast.rs @@ -3,7 +3,6 @@ use std::fmt::Write; use std::hash::Hash; use std::ops::Add; -use comemo::Prehashed; use ecow::{eco_format, EcoString}; use smallvec::SmallVec; use unicode_math_class::MathClass; @@ -98,20 +97,6 @@ impl<T: NativeElement + Reflect> Reflect for Packed<T> { } } -impl<T: Reflect> Reflect for Prehashed<T> { - fn input() -> CastInfo { - T::input() - } - - fn output() -> CastInfo { - T::output() - } - - fn castable(value: &Value) -> bool { - T::castable(value) - } -} - impl<T: Reflect> Reflect for StrResult<T> { fn input() -> CastInfo { T::input() @@ -206,12 +191,6 @@ impl<T: IntoValue> IntoValue for Spanned<T> { } } -impl<T: IntoValue + Hash + 'static> IntoValue for Prehashed<T> { - fn into_value(self) -> Value { - self.into_inner().into_value() - } -} - /// Cast a Rust type or result into a [`SourceResult<Value>`]. /// /// Converts `T`, [`StrResult<T>`], or [`SourceResult<T>`] into @@ -278,12 +257,6 @@ impl<T: NativeElement + FromValue> FromValue for Packed<T> { } } -impl<T: FromValue + Hash + 'static> FromValue for Prehashed<T> { - fn from_value(value: Value) -> StrResult<Self> { - Ok(Self::new(T::from_value(value)?)) - } -} - impl<T: FromValue> FromValue<Spanned<Value>> for T { fn from_value(value: Spanned<Value>) -> StrResult<Self> { T::from_value(value.v) diff --git a/crates/typst/src/foundations/content.rs b/crates/typst/src/foundations/content.rs index 86e75eb5..6d937dfb 100644 --- a/crates/typst/src/foundations/content.rs +++ b/crates/typst/src/foundations/content.rs @@ -6,7 +6,6 @@ use std::marker::PhantomData; use std::ops::{Add, AddAssign, Deref, DerefMut}; use std::sync::Arc; -use comemo::Prehashed; use ecow::{eco_format, EcoString}; use serde::{Serialize, Serializer}; use smallvec::smallvec; @@ -23,7 +22,7 @@ use crate::model::{Destination, EmphElem, StrongElem}; use crate::realize::{Behave, Behaviour}; use crate::syntax::Span; use crate::text::UnderlineElem; -use crate::util::{fat, BitSet}; +use crate::util::{fat, BitSet, LazyHash}; /// A piece of document content. /// @@ -80,7 +79,7 @@ pub struct Content { /// The inner representation behind the `Arc`. #[derive(Hash)] -struct Inner<T: ?Sized> { +struct Inner<T: ?Sized + 'static> { /// An optional label attached to the element. label: Option<Label>, /// The element's location which identifies it in the layouted output. @@ -91,7 +90,7 @@ struct Inner<T: ?Sized> { /// recipe from the top of the style chain (counting from 1). lifecycle: BitSet, /// The element's raw data. - elem: T, + elem: LazyHash<T>, } impl Content { @@ -102,7 +101,7 @@ impl Content { label: None, location: None, lifecycle: BitSet::new(), - elem, + elem: elem.into(), }), span: Span::detached(), } @@ -235,9 +234,9 @@ impl Content { let Some(first) = iter.next() else { return Self::empty() }; let Some(second) = iter.next() else { return first }; SequenceElem::new( - std::iter::once(Prehashed::new(first)) - .chain(std::iter::once(Prehashed::new(second))) - .chain(iter.map(Prehashed::new)) + std::iter::once(first) + .chain(std::iter::once(second)) + .chain(iter) .collect(), ) .into() @@ -379,7 +378,7 @@ impl Content { style_elem.styles.apply(styles); self } else { - StyledElem::new(Prehashed::new(self), styles).into() + StyledElem::new(self, styles).into() } } @@ -620,11 +619,11 @@ impl Add for Content { lhs } (Some(seq_lhs), None) => { - seq_lhs.children.push(Prehashed::new(rhs)); + seq_lhs.children.push(rhs); lhs } (None, Some(rhs_seq)) => { - rhs_seq.children.insert(0, Prehashed::new(lhs)); + rhs_seq.children.insert(0, lhs); rhs } (None, None) => Self::sequence([lhs, rhs]), @@ -643,15 +642,12 @@ impl<'a> Add<&'a Self> for Content { lhs } (Some(seq_lhs), None) => { - seq_lhs.children.push(Prehashed::new(rhs.clone())); + seq_lhs.children.push(rhs.clone()); lhs } (None, Some(_)) => { let mut rhs = rhs.clone(); - rhs.to_packed_mut::<SequenceElem>() - .unwrap() - .children - .insert(0, Prehashed::new(lhs)); + rhs.to_packed_mut::<SequenceElem>().unwrap().children.insert(0, lhs); rhs } (None, None) => Self::sequence([lhs, rhs.clone()]), @@ -713,7 +709,7 @@ impl<T: NativeElement> Bounds for T { label: inner.label, location: inner.location, lifecycle: inner.lifecycle.clone(), - elem: self.clone(), + elem: LazyHash::with_hash(self.clone(), inner.elem.hash()), }), span, } @@ -845,7 +841,7 @@ impl<T: NativeElement> Deref for Packed<T> { // an element of type `T`. // - This downcast works the same way as dyn Any's does. We can't reuse // that one because we don't want to pay the cost for every deref. - let elem = &self.0.inner.elem; + let elem = &*self.0.inner.elem; unsafe { &*(elem as *const dyn Bounds as *const T) } } } @@ -858,7 +854,7 @@ impl<T: NativeElement> DerefMut for Packed<T> { // - We have guaranteed unique access thanks to `make_mut`. // - This downcast works the same way as dyn Any's does. We can't reuse // that one because we don't want to pay the cost for every deref. - let elem = &mut self.0.make_mut().elem; + let elem = &mut *self.0.make_mut().elem; unsafe { &mut *(elem as *mut dyn Bounds as *mut T) } } } @@ -874,7 +870,7 @@ impl<T: NativeElement + Debug> Debug for Packed<T> { pub struct SequenceElem { /// The elements. #[required] - pub children: Vec<Prehashed<Content>>, + pub children: Vec<Content>, } impl Debug for SequenceElem { @@ -894,10 +890,7 @@ impl Default for SequenceElem { impl PartialEq for SequenceElem { fn eq(&self, other: &Self) -> bool { - self.children - .iter() - .map(|c| &**c) - .eq(other.children.iter().map(|c| &**c)) + self.children.iter().eq(other.children.iter()) } } @@ -926,7 +919,7 @@ impl Repr for SequenceElem { pub struct StyledElem { /// The content. #[required] - pub child: Prehashed<Content>, + pub child: Content, /// The styles. #[required] pub styles: Styles, @@ -943,7 +936,7 @@ impl Debug for StyledElem { impl PartialEq for StyledElem { fn eq(&self, other: &Self) -> bool { - *self.child == *other.child + self.child == other.child } } diff --git a/crates/typst/src/foundations/func.rs b/crates/typst/src/foundations/func.rs index 70d0ec31..6062da17 100644 --- a/crates/typst/src/foundations/func.rs +++ b/crates/typst/src/foundations/func.rs @@ -1,7 +1,7 @@ use std::fmt::{self, Debug, Formatter}; use std::sync::Arc; -use comemo::{Prehashed, TrackedMut}; +use comemo::TrackedMut; use ecow::{eco_format, EcoString}; use once_cell::sync::Lazy; @@ -12,7 +12,7 @@ use crate::foundations::{ Type, Value, }; use crate::syntax::{ast, Span, SyntaxNode}; -use crate::util::Static; +use crate::util::{LazyHash, Static}; #[doc(inline)] pub use typst_macros::func; @@ -141,7 +141,7 @@ enum Repr { /// A function for an element. Element(Element), /// A user-defined closure. - Closure(Arc<Prehashed<Closure>>), + Closure(Arc<LazyHash<Closure>>), /// A nested function with pre-applied arguments. With(Arc<(Func, Args)>), } @@ -485,7 +485,7 @@ impl Closure { impl From<Closure> for Func { fn from(closure: Closure) -> Self { - Repr::Closure(Arc::new(Prehashed::new(closure))).into() + Repr::Closure(Arc::new(LazyHash::new(closure))).into() } } diff --git a/crates/typst/src/foundations/styles.rs b/crates/typst/src/foundations/styles.rs index fb8e5601..30213cfc 100644 --- a/crates/typst/src/foundations/styles.rs +++ b/crates/typst/src/foundations/styles.rs @@ -3,7 +3,6 @@ use std::fmt::{self, Debug, Formatter}; use std::hash::{Hash, Hasher}; use std::{mem, ptr}; -use comemo::Prehashed; use ecow::{eco_vec, EcoString, EcoVec}; use smallvec::SmallVec; @@ -15,6 +14,7 @@ use crate::foundations::{ }; use crate::syntax::Span; use crate::text::{FontFamily, FontList, TextElem}; +use crate::util::LazyHash; /// Provides access to active styles. /// @@ -65,7 +65,7 @@ impl Show for Packed<StyleElem> { /// A list of style properties. #[ty(cast)] #[derive(Default, PartialEq, Clone, Hash)] -pub struct Styles(EcoVec<Prehashed<Style>>); +pub struct Styles(EcoVec<LazyHash<Style>>); impl Styles { /// Create a new, empty style list. @@ -89,7 +89,7 @@ impl Styles { /// style map, `self` contributes the outer values and `value` is the inner /// one. pub fn set(&mut self, style: impl Into<Style>) { - self.0.push(Prehashed::new(style.into())); + self.0.push(LazyHash::new(style.into())); } /// Remove the style that was last set. @@ -105,22 +105,20 @@ impl Styles { /// Apply one outer styles. pub fn apply_one(&mut self, outer: Style) { - self.0.insert(0, Prehashed::new(outer)); + self.0.insert(0, LazyHash::new(outer)); } /// Apply a slice of outer styles. - pub fn apply_slice(&mut self, outer: &[Prehashed<Style>]) { + pub fn apply_slice(&mut self, outer: &[LazyHash<Style>]) { self.0 = outer.iter().cloned().chain(mem::take(self).0).collect(); } /// Add an origin span to all contained properties. pub fn spanned(mut self, span: Span) -> Self { for entry in self.0.make_mut() { - entry.update(|entry| { - if let Style::Property(property) = entry { - property.span = Some(span); - } - }); + if let Style::Property(property) = &mut **entry { + property.span = Some(span); + } } self } @@ -147,15 +145,15 @@ impl Styles { } } -impl From<Prehashed<Style>> for Styles { - fn from(style: Prehashed<Style>) -> Self { +impl From<LazyHash<Style>> for Styles { + fn from(style: LazyHash<Style>) -> Self { Self(eco_vec![style]) } } impl From<Style> for Styles { fn from(style: Style) -> Self { - Self(eco_vec![Prehashed::new(style)]) + Self(eco_vec![LazyHash::new(style)]) } } @@ -262,8 +260,8 @@ impl Property { } /// Turn this property into prehashed style. - pub fn wrap(self) -> Prehashed<Style> { - Prehashed::new(Style::Property(self)) + pub fn wrap(self) -> LazyHash<Style> { + LazyHash::new(Style::Property(self)) } } @@ -457,7 +455,7 @@ cast! { #[derive(Default, Clone, Copy, Hash)] pub struct StyleChain<'a> { /// The first link of this chain. - head: &'a [Prehashed<Style>], + head: &'a [LazyHash<Style>], /// The remaining links in the chain. tail: Option<&'a Self>, } @@ -616,7 +614,7 @@ pub trait Chainable { fn chain<'a>(&'a self, outer: &'a StyleChain<'_>) -> StyleChain<'a>; } -impl Chainable for Prehashed<Style> { +impl Chainable for LazyHash<Style> { fn chain<'a>(&'a self, outer: &'a StyleChain<'_>) -> StyleChain<'a> { StyleChain { head: std::slice::from_ref(self), @@ -625,7 +623,7 @@ impl Chainable for Prehashed<Style> { } } -impl Chainable for [Prehashed<Style>] { +impl Chainable for [LazyHash<Style>] { fn chain<'a>(&'a self, outer: &'a StyleChain<'_>) -> StyleChain<'a> { if self.is_empty() { *outer @@ -635,7 +633,7 @@ impl Chainable for [Prehashed<Style>] { } } -impl<const N: usize> Chainable for [Prehashed<Style>; N] { +impl<const N: usize> Chainable for [LazyHash<Style>; N] { fn chain<'a>(&'a self, outer: &'a StyleChain<'_>) -> StyleChain<'a> { Chainable::chain(self.as_slice(), outer) } @@ -649,7 +647,7 @@ impl Chainable for Styles { /// An iterator over the entries in a style chain. pub struct Entries<'a> { - inner: std::slice::Iter<'a, Prehashed<Style>>, + inner: std::slice::Iter<'a, LazyHash<Style>>, links: Links<'a>, } @@ -674,7 +672,7 @@ impl<'a> Iterator for Entries<'a> { pub struct Links<'a>(Option<StyleChain<'a>>); impl<'a> Iterator for Links<'a> { - type Item = &'a [Prehashed<Style>]; + type Item = &'a [LazyHash<Style>]; fn next(&mut self) -> Option<Self::Item> { let StyleChain { head, tail } = self.0?; diff --git a/crates/typst/src/introspection/introspector.rs b/crates/typst/src/introspection/introspector.rs index f8270025..47d40476 100644 --- a/crates/typst/src/introspection/introspector.rs +++ b/crates/typst/src/introspection/introspector.rs @@ -4,7 +4,6 @@ use std::hash::Hash; use std::num::NonZeroUsize; use std::sync::RwLock; -use comemo::Prehashed; use ecow::{eco_format, EcoVec}; use indexmap::IndexMap; use smallvec::SmallVec; @@ -22,7 +21,7 @@ pub struct Introspector { /// The number of pages in the document. pages: usize, /// All introspectable elements. - elems: IndexMap<Location, (Prehashed<Content>, Position)>, + elems: IndexMap<Location, (Content, Position)>, /// Maps labels to their indices in the element list. We use a smallvec such /// that if the label is unique, we don't need to allocate. labels: HashMap<Label, SmallVec<[usize; 1]>>, @@ -66,7 +65,6 @@ impl Introspector { if !self.elems.contains_key(&content.location().unwrap()) => { let pos = pos.transform(ts); - let content = Prehashed::new(content.clone()); let ret = self.elems.insert( content.location().unwrap(), (content.clone(), Position { page, point: pos }), @@ -84,12 +82,12 @@ impl Introspector { } /// Iterate over all locatable elements. - pub fn all(&self) -> impl Iterator<Item = &Prehashed<Content>> + '_ { + pub fn all(&self) -> impl Iterator<Item = &Content> + '_ { self.elems.values().map(|(c, _)| c) } /// Get an element by its location. - fn get(&self, location: &Location) -> Option<&Prehashed<Content>> { + fn get(&self, location: &Location) -> Option<&Content> { self.elems.get(location).map(|(elem, _)| elem) } @@ -101,11 +99,7 @@ impl Introspector { } /// Perform a binary search for `elem` among the `list`. - fn binary_search( - &self, - list: &[Prehashed<Content>], - elem: &Content, - ) -> Result<usize, usize> { + fn binary_search(&self, list: &[Content], elem: &Content) -> Result<usize, usize> { list.binary_search_by_key(&self.index(elem), |elem| self.index(elem)) } } @@ -113,7 +107,7 @@ impl Introspector { #[comemo::track] impl Introspector { /// Query for all matching elements. - pub fn query(&self, selector: &Selector) -> EcoVec<Prehashed<Content>> { + pub fn query(&self, selector: &Selector) -> EcoVec<Content> { let hash = crate::util::hash128(selector); if let Some(output) = self.queries.get(hash) { return output; @@ -201,7 +195,7 @@ impl Introspector { } /// Query for the first element that matches the selector. - pub fn query_first(&self, selector: &Selector) -> Option<Prehashed<Content>> { + pub fn query_first(&self, selector: &Selector) -> Option<Content> { match selector { Selector::Location(location) => self.get(location).cloned(), _ => self.query(selector).first().cloned(), @@ -209,7 +203,7 @@ impl Introspector { } /// Query for a unique element with the label. - pub fn query_label(&self, label: Label) -> StrResult<&Prehashed<Content>> { + pub fn query_label(&self, label: Label) -> StrResult<&Content> { let indices = self.labels.get(&label).ok_or_else(|| { eco_format!("label `{}` does not exist in the document", label.repr()) })?; @@ -268,14 +262,14 @@ impl Debug for Introspector { /// Caches queries. #[derive(Default)] -struct QueryCache(RwLock<HashMap<u128, EcoVec<Prehashed<Content>>>>); +struct QueryCache(RwLock<HashMap<u128, EcoVec<Content>>>); impl QueryCache { - fn get(&self, hash: u128) -> Option<EcoVec<Prehashed<Content>>> { + fn get(&self, hash: u128) -> Option<EcoVec<Content>> { self.0.read().unwrap().get(&hash).cloned() } - fn insert(&self, hash: u128, output: EcoVec<Prehashed<Content>>) { + fn insert(&self, hash: u128, output: EcoVec<Content>) { self.0.write().unwrap().insert(hash, output); } diff --git a/crates/typst/src/introspection/query.rs b/crates/typst/src/introspection/query.rs index 7b7d581c..e3446576 100644 --- a/crates/typst/src/introspection/query.rs +++ b/crates/typst/src/introspection/query.rs @@ -156,7 +156,5 @@ pub fn query( ) -> Array { let _ = location; let vec = engine.introspector.query(&target.0); - vec.into_iter() - .map(|elem| Value::Content(elem.into_inner())) - .collect() + vec.into_iter().map(Value::Content).collect() } diff --git a/crates/typst/src/layout/flow.rs b/crates/typst/src/layout/flow.rs index 4308182d..d35b39cc 100644 --- a/crates/typst/src/layout/flow.rs +++ b/crates/typst/src/layout/flow.rs @@ -1,7 +1,5 @@ use std::fmt::{self, Debug, Formatter}; -use comemo::Prehashed; - use crate::diag::{bail, SourceResult}; use crate::engine::Engine; use crate::foundations::{ @@ -24,7 +22,7 @@ use crate::util::Numeric; pub struct FlowElem { /// The children that will be arranges into a flow. #[variadic] - pub children: Vec<Prehashed<Content>>, + pub children: Vec<Content>, } impl LayoutMultiple for Packed<FlowElem> { @@ -43,7 +41,7 @@ impl LayoutMultiple for Packed<FlowElem> { } let mut layouter = FlowLayouter::new(regions, styles); - for mut child in self.children().iter().map(|c| &**c) { + for mut child in self.children().iter() { let outer = styles; let mut styles = styles; if let Some(styled) = child.to_packed::<StyledElem>() { diff --git a/crates/typst/src/layout/inline/mod.rs b/crates/typst/src/layout/inline/mod.rs index 17407bfa..f579b8a3 100644 --- a/crates/typst/src/layout/inline/mod.rs +++ b/crates/typst/src/layout/inline/mod.rs @@ -1,7 +1,7 @@ mod linebreak; mod shaping; -use comemo::{Prehashed, Tracked, TrackedMut}; +use comemo::{Tracked, TrackedMut}; use unicode_bidi::{BidiInfo, Level as BidiLevel}; use unicode_script::{Script, UnicodeScript}; @@ -30,7 +30,7 @@ use crate::World; /// Layouts content inline. pub(crate) fn layout_inline( - children: &[Prehashed<Content>], + children: &[Content], engine: &mut Engine, styles: StyleChain, consecutive: bool, @@ -40,7 +40,7 @@ pub(crate) fn layout_inline( #[comemo::memoize] #[allow(clippy::too_many_arguments)] fn cached( - children: &[Prehashed<Content>], + children: &[Content], world: Tracked<dyn World + '_>, introspector: Tracked<Introspector>, route: Tracked<Route>, @@ -404,7 +404,7 @@ impl<'a> Line<'a> { /// also performs string-level preprocessing like case transformations. #[allow(clippy::type_complexity)] fn collect<'a>( - children: &'a [Prehashed<Content>], + children: &'a [Content], engine: &mut Engine<'_>, styles: &'a StyleChain<'a>, region: Size, @@ -414,7 +414,7 @@ fn collect<'a>( let mut quoter = SmartQuoter::new(); let mut segments = Vec::with_capacity(2 + children.len()); let mut spans = SpanMapper::new(); - let mut iter = children.iter().map(|c| &**c).peekable(); + let mut iter = children.iter().peekable(); let first_line_indent = ParElem::first_line_indent_in(*styles); if !first_line_indent.is_zero() @@ -539,7 +539,7 @@ fn collect<'a>( /// Prepare paragraph layout by shaping the whole paragraph. fn prepare<'a>( engine: &mut Engine, - children: &'a [Prehashed<Content>], + children: &'a [Content], text: &'a str, segments: Vec<(Segment<'a>, StyleChain<'a>)>, spans: SpanMapper, @@ -752,7 +752,7 @@ fn is_compatible(a: Script, b: Script) -> bool { /// paragraph. fn shared_get<T: PartialEq>( styles: StyleChain<'_>, - children: &[Prehashed<Content>], + children: &[Content], getter: fn(StyleChain) -> T, ) -> Option<T> { let value = getter(styles); diff --git a/crates/typst/src/math/ctx.rs b/crates/typst/src/math/ctx.rs index 9c2623e4..9acf0735 100644 --- a/crates/typst/src/math/ctx.rs +++ b/crates/typst/src/math/ctx.rs @@ -1,6 +1,5 @@ use std::f64::consts::SQRT_2; -use comemo::Prehashed; use ecow::EcoString; use rustybuzz::Feature; use ttf_parser::gsub::{AlternateSubstitution, SingleSubstitution, SubstitutionSubtable}; @@ -288,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![Prehashed::new(text)]); + let par = ParElem::new(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/style.rs b/crates/typst/src/math/style.rs index 876033d5..717b23c3 100644 --- a/crates/typst/src/math/style.rs +++ b/crates/typst/src/math/style.rs @@ -1,9 +1,8 @@ -use comemo::Prehashed; - use crate::foundations::{func, Cast, Content, Smart, Style, StyleChain}; use crate::layout::Abs; use crate::math::{EquationElem, MathContext}; use crate::text::TextElem; +use crate::util::LazyHash; /// Bold font style in math. /// @@ -253,17 +252,17 @@ pub fn scaled_font_size(ctx: &MathContext, styles: StyleChain) -> Abs { } /// Styles something as cramped. -pub fn style_cramped() -> Prehashed<Style> { +pub fn style_cramped() -> LazyHash<Style> { EquationElem::set_cramped(true).wrap() } /// The style for subscripts in the current style. -pub fn style_for_subscript(styles: StyleChain) -> [Prehashed<Style>; 2] { +pub fn style_for_subscript(styles: StyleChain) -> [LazyHash<Style>; 2] { [style_for_superscript(styles), EquationElem::set_cramped(true).wrap()] } /// The style for superscripts in the current style. -pub fn style_for_superscript(styles: StyleChain) -> Prehashed<Style> { +pub fn style_for_superscript(styles: StyleChain) -> LazyHash<Style> { EquationElem::set_size(match EquationElem::size_in(styles) { MathSize::Display | MathSize::Text => MathSize::Script, MathSize::Script | MathSize::ScriptScript => MathSize::ScriptScript, @@ -272,7 +271,7 @@ pub fn style_for_superscript(styles: StyleChain) -> Prehashed<Style> { } /// The style for numerators in the current style. -pub fn style_for_numerator(styles: StyleChain) -> Prehashed<Style> { +pub fn style_for_numerator(styles: StyleChain) -> LazyHash<Style> { EquationElem::set_size(match EquationElem::size_in(styles) { MathSize::Display => MathSize::Text, MathSize::Text => MathSize::Script, @@ -282,7 +281,7 @@ pub fn style_for_numerator(styles: StyleChain) -> Prehashed<Style> { } /// The style for denominators in the current style. -pub fn style_for_denominator(styles: StyleChain) -> [Prehashed<Style>; 2] { +pub fn style_for_denominator(styles: StyleChain) -> [LazyHash<Style>; 2] { [style_for_numerator(styles), EquationElem::set_cramped(true).wrap()] } diff --git a/crates/typst/src/model/bibliography.rs b/crates/typst/src/model/bibliography.rs index ca7695d9..ab14ab49 100644 --- a/crates/typst/src/model/bibliography.rs +++ b/crates/typst/src/model/bibliography.rs @@ -6,7 +6,7 @@ use std::num::NonZeroUsize; use std::path::Path; use std::sync::Arc; -use comemo::{Prehashed, Tracked}; +use comemo::Tracked; use ecow::{eco_format, EcoString, EcoVec}; use hayagriva::archive::ArchivedStyle; use hayagriva::io::BibLaTeXError; @@ -40,7 +40,7 @@ use crate::syntax::{Span, Spanned}; use crate::text::{ FontStyle, Lang, LocalName, Region, SubElem, SuperElem, TextElem, WeightDelta, }; -use crate::util::{option_eq, NonZeroExt, PicoStr}; +use crate::util::{option_eq, LazyHash, NonZeroExt, PicoStr}; use crate::World; /// A bibliography / reference listing. @@ -438,7 +438,7 @@ fn format_biblatex_error(path: &str, src: &str, errors: Vec<BibLaTeXError>) -> E #[derive(Debug, Clone, PartialEq, Hash)] pub struct CslStyle { name: Option<EcoString>, - style: Arc<Prehashed<citationberg::IndependentStyle>>, + style: Arc<LazyHash<citationberg::IndependentStyle>>, } impl CslStyle { @@ -495,7 +495,7 @@ impl CslStyle { match hayagriva::archive::ArchivedStyle::by_name(name).map(ArchivedStyle::get) { Some(citationberg::Style::Independent(style)) => Ok(Self { name: Some(name.into()), - style: Arc::new(Prehashed::new(style)), + style: Arc::new(LazyHash::new(style)), }), _ => bail!("unknown style: `{name}`"), } @@ -506,7 +506,7 @@ impl CslStyle { pub fn from_data(data: &Bytes) -> StrResult<CslStyle> { let text = std::str::from_utf8(data.as_slice()).map_err(FileError::from)?; citationberg::IndependentStyle::from_xml(text) - .map(|style| Self { name: None, style: Arc::new(Prehashed::new(style)) }) + .map(|style| Self { name: None, style: Arc::new(LazyHash::new(style)) }) .map_err(|err| eco_format!("failed to load CSL style ({err})")) } @@ -606,7 +606,7 @@ struct Generator<'a> { /// The document's bibliography. bibliography: Packed<BibliographyElem>, /// The document's citation groups. - groups: EcoVec<Prehashed<Content>>, + groups: EcoVec<Content>, /// Details about each group that are accumulated while driving hayagriva's /// bibliography driver and needed when processing hayagriva's output. infos: Vec<GroupInfo>, diff --git a/crates/typst/src/model/outline.rs b/crates/typst/src/model/outline.rs index 8285673a..a50bd937 100644 --- a/crates/typst/src/model/outline.rs +++ b/crates/typst/src/model/outline.rs @@ -213,7 +213,7 @@ impl Show for Packed<OutlineElem> { let Some(entry) = OutlineEntry::from_outlinable( engine, self.span(), - elem.clone().into_inner(), + elem.clone(), self.fill(styles), )? else { diff --git a/crates/typst/src/model/par.rs b/crates/typst/src/model/par.rs index 4594e7fd..629613e8 100644 --- a/crates/typst/src/model/par.rs +++ b/crates/typst/src/model/par.rs @@ -1,7 +1,5 @@ use std::fmt::{self, Debug, Formatter}; -use comemo::Prehashed; - use crate::diag::SourceResult; use crate::engine::Engine; use crate::foundations::{ @@ -106,7 +104,7 @@ pub struct ParElem { /// The paragraph's children. #[internal] #[variadic] - pub children: Vec<Prehashed<Content>>, + pub children: Vec<Content>, } impl Construct for ParElem { diff --git a/crates/typst/src/model/reference.rs b/crates/typst/src/model/reference.rs index 00ab8b4d..085313f1 100644 --- a/crates/typst/src/model/reference.rs +++ b/crates/typst/src/model/reference.rs @@ -151,7 +151,7 @@ impl Synthesize for Packed<RefElem> { let target = *elem.target(); if !BibliographyElem::has(engine, target) { if let Ok(found) = engine.introspector.query_label(target).cloned() { - elem.push_element(Some(found.into_inner())); + elem.push_element(Some(found)); return Ok(()); } } diff --git a/crates/typst/src/util/hash.rs b/crates/typst/src/util/hash.rs new file mode 100644 index 00000000..2b6c5857 --- /dev/null +++ b/crates/typst/src/util/hash.rs @@ -0,0 +1,161 @@ +use std::any::Any; +use std::fmt::{self, Debug}; +use std::hash::{Hash, Hasher}; +use std::ops::{Deref, DerefMut}; + +use portable_atomic::{AtomicU128, Ordering}; +use siphasher::sip128::{Hasher128, SipHasher13}; + +/// A wrapper type with lazily-computed hash. +/// +/// This is useful if you want to pass large values of `T` to memoized +/// functions. Especially recursive structures like trees benefit from +/// intermediate prehashed nodes. +/// +/// Note that for a value `v` of type `T`, `hash(v)` is not necessarily equal to +/// `hash(LazyHash::new(v))`. Writing the precomputed hash into a hasher's +/// state produces different output than writing the value's parts directly. +/// However, that seldomly matters as you are typically either dealing with +/// values of type `T` or with values of type `LazyHash<T>`, not a mix of both. +/// +/// # Equality +/// Because Typst uses high-quality 128 bit hashes in all places, the risk of a +/// hash collision is reduced to an absolute minimum. Therefore, this type +/// additionally provides `PartialEq` and `Eq` implementations that compare by +/// hash instead of by value. For this to be correct, your hash implementation +/// **must feed all information relevant to the `PartialEq` impl to the +/// hasher.** +/// +/// # Usage +/// If the value is expected to be cloned, it is best used inside of an `Arc` +/// or `Rc` to best re-use the hash once it has been computed. +pub struct LazyHash<T: ?Sized> { + /// The hash for the value. + hash: AtomicU128, + /// The underlying value. + value: T, +} + +impl<T: Default> Default for LazyHash<T> { + #[inline] + fn default() -> Self { + Self::new(Default::default()) + } +} + +impl<T> LazyHash<T> { + /// Wrap an item without pre-computed hash. + #[inline] + pub fn new(value: T) -> Self { + Self { hash: AtomicU128::new(0), value } + } + + /// Wrap an item with a pre-computed hash. + /// + /// **Important:** The hash must be correct for the value. This cannot be + /// enforced at compile time, so use with caution. + #[inline] + pub fn with_hash(value: T, hash: u128) -> Self { + Self { hash: AtomicU128::new(hash), value } + } + + /// Return the wrapped value. + #[inline] + pub fn into_inner(self) -> T { + self.value + } +} + +impl<T: Hash + ?Sized + 'static> LazyHash<T> { + /// Get the hash, returns zero if not computed yet. + #[inline] + pub fn hash(&self) -> u128 { + self.hash.load(Ordering::SeqCst) + } + + /// Reset the hash to zero. + #[inline] + fn reset_hash(&mut self) { + // Because we have a mutable reference, we can skip the atomic + *self.hash.get_mut() = 0; + } + + /// Get the hash or compute it if not set yet. + #[inline] + fn get_or_set_hash(&self) -> u128 { + let hash = self.hash(); + if hash == 0 { + let hashed = hash_item(&self.value); + self.hash.store(hashed, Ordering::SeqCst); + hashed + } else { + hash + } + } +} + +/// Hash the item. +#[inline] +fn hash_item<T: Hash + ?Sized + 'static>(item: &T) -> u128 { + // Also hash the TypeId because the type might be converted + // through an unsized coercion. + let mut state = SipHasher13::new(); + item.type_id().hash(&mut state); + item.hash(&mut state); + state.finish128().as_u128() +} + +impl<T: Hash + ?Sized + 'static> Hash for LazyHash<T> { + #[inline] + fn hash<H: Hasher>(&self, state: &mut H) { + state.write_u128(self.get_or_set_hash()); + } +} + +impl<T> From<T> for LazyHash<T> { + #[inline] + fn from(value: T) -> Self { + Self::new(value) + } +} + +impl<T: Hash + ?Sized + 'static> Eq for LazyHash<T> {} + +impl<T: Hash + ?Sized + 'static> PartialEq for LazyHash<T> { + #[inline] + fn eq(&self, other: &Self) -> bool { + self.get_or_set_hash() == other.get_or_set_hash() + } +} + +impl<T: ?Sized> Deref for LazyHash<T> { + type Target = T; + + #[inline] + fn deref(&self) -> &Self::Target { + &self.value + } +} + +impl<T: Hash + ?Sized + 'static> DerefMut for LazyHash<T> { + #[inline] + fn deref_mut(&mut self) -> &mut Self::Target { + self.reset_hash(); + &mut self.value + } +} + +impl<T: Hash + Clone + 'static> Clone for LazyHash<T> { + fn clone(&self) -> Self { + Self { + hash: AtomicU128::new(self.hash()), + value: self.value.clone(), + } + } +} + +impl<T: Debug> Debug for LazyHash<T> { + fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result { + self.value.fmt(f) + } +} diff --git a/crates/typst/src/util/mod.rs b/crates/typst/src/util/mod.rs index 0ccc0a31..3a81bf55 100644 --- a/crates/typst/src/util/mod.rs +++ b/crates/typst/src/util/mod.rs @@ -6,11 +6,13 @@ pub mod fat; mod macros; mod bitset; mod deferred; +mod hash; mod pico; mod scalar; pub use self::bitset::BitSet; pub use self::deferred::Deferred; +pub use self::hash::LazyHash; pub use self::pico::PicoStr; pub use self::scalar::Scalar; diff --git a/crates/typst/src/visualize/image/mod.rs b/crates/typst/src/visualize/image/mod.rs index dc58bf80..e7c91cd6 100644 --- a/crates/typst/src/visualize/image/mod.rs +++ b/crates/typst/src/visualize/image/mod.rs @@ -10,7 +10,7 @@ use std::ffi::OsStr; use std::fmt::{self, Debug, Formatter}; use std::sync::Arc; -use comemo::{Prehashed, Tracked}; +use comemo::Tracked; use ecow::EcoString; use crate::diag::{bail, At, SourceResult, StrResult}; @@ -27,7 +27,7 @@ use crate::loading::Readable; use crate::model::Figurable; use crate::syntax::{Span, Spanned}; use crate::text::{families, Lang, LocalName, Region}; -use crate::util::{option_eq, Numeric}; +use crate::util::{option_eq, LazyHash, Numeric}; use crate::visualize::Path; use crate::World; @@ -299,7 +299,7 @@ pub enum ImageFit { /// /// Values of this type are cheap to clone and hash. #[derive(Clone, Hash, Eq, PartialEq)] -pub struct Image(Arc<Prehashed<Repr>>); +pub struct Image(Arc<LazyHash<Repr>>); /// The internal representation. #[derive(Hash)] @@ -337,7 +337,7 @@ impl Image { } }; - Ok(Self(Arc::new(Prehashed::new(Repr { kind, alt })))) + Ok(Self(Arc::new(LazyHash::new(Repr { kind, alt })))) } /// Create a possibly font-dependant image from a buffer and a format. @@ -359,7 +359,7 @@ impl Image { } }; - Ok(Self(Arc::new(Prehashed::new(Repr { kind, alt })))) + Ok(Self(Arc::new(LazyHash::new(Repr { kind, alt })))) } /// The raw image data. |