diff options
Diffstat (limited to 'crates/typst-library/src/introspection')
| -rw-r--r-- | crates/typst-library/src/introspection/counter.rs | 856 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/here.rs | 52 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/introspector.rs | 453 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/locate.rs | 119 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/location.rs | 113 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/locator.rs | 350 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/metadata.rs | 38 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/mod.rs | 53 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/query.rs | 171 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/state.rs | 476 | ||||
| -rw-r--r-- | crates/typst-library/src/introspection/tag.rs | 73 |
11 files changed, 2754 insertions, 0 deletions
diff --git a/crates/typst-library/src/introspection/counter.rs b/crates/typst-library/src/introspection/counter.rs new file mode 100644 index 00000000..2e7180c6 --- /dev/null +++ b/crates/typst-library/src/introspection/counter.rs @@ -0,0 +1,856 @@ +use std::num::NonZeroUsize; +use std::str::FromStr; + +use comemo::{Track, Tracked, TrackedMut}; +use ecow::{eco_format, eco_vec, EcoString, EcoVec}; +use smallvec::{smallvec, SmallVec}; +use typst_syntax::Span; +use typst_utils::NonZeroExt; + +use crate::diag::{bail, warning, At, HintedStrResult, SourceResult}; +use crate::engine::{Engine, Route, Sink, Traced}; +use crate::foundations::{ + cast, elem, func, scope, select_where, ty, Args, Array, Construct, Content, Context, + Element, Func, IntoValue, Label, LocatableSelector, NativeElement, Packed, Repr, + Selector, Show, Smart, Str, StyleChain, Value, +}; +use crate::introspection::{Introspector, Locatable, Location, Tag}; +use crate::layout::{Frame, FrameItem, PageElem}; +use crate::math::EquationElem; +use crate::model::{FigureElem, FootnoteElem, HeadingElem, Numbering, NumberingPattern}; +use crate::routines::Routines; +use crate::World; + +/// Counts through pages, elements, and more. +/// +/// With the counter function, you can access and modify counters for pages, +/// headings, figures, and more. Moreover, you can define custom counters for +/// other things you want to count. +/// +/// Since counters change throughout the course of the document, their current +/// value is _contextual._ It is recommended to read the chapter on [context] +/// before continuing here. +/// +/// # Accessing a counter { #accessing } +/// To access the raw value of a counter, we can use the [`get`]($counter.get) +/// function. This function returns an [array]: Counters can have multiple +/// levels (in the case of headings for sections, subsections, and so on), and +/// each item in the array corresponds to one level. +/// +/// ```example +/// #set heading(numbering: "1.") +/// +/// = Introduction +/// Raw value of heading counter is +/// #context counter(heading).get() +/// ``` +/// +/// # Displaying a counter { #displaying } +/// Often, we want to display the value of a counter in a more human-readable +/// way. To do that, we can call the [`display`]($counter.display) function on +/// the counter. This function retrieves the current counter value and formats +/// it either with a provided or with an automatically inferred [numbering]. +/// +/// ```example +/// #set heading(numbering: "1.") +/// +/// = Introduction +/// Some text here. +/// +/// = Background +/// The current value is: #context { +/// counter(heading).display() +/// } +/// +/// Or in roman numerals: #context { +/// counter(heading).display("I") +/// } +/// ``` +/// +/// # Modifying a counter { #modifying } +/// To modify a counter, you can use the `step` and `update` methods: +/// +/// - The `step` method increases the value of the counter by one. Because +/// counters can have multiple levels , it optionally takes a `level` +/// argument. If given, the counter steps at the given depth. +/// +/// - The `update` method allows you to arbitrarily modify the counter. In its +/// basic form, you give it an integer (or an array for multiple levels). For +/// more flexibility, you can instead also give it a function that receives +/// the current value and returns a new value. +/// +/// The heading counter is stepped before the heading is displayed, so +/// `Analysis` gets the number seven even though the counter is at six after the +/// second update. +/// +/// ```example +/// #set heading(numbering: "1.") +/// +/// = Introduction +/// #counter(heading).step() +/// +/// = Background +/// #counter(heading).update(3) +/// #counter(heading).update(n => n * 2) +/// +/// = Analysis +/// Let's skip 7.1. +/// #counter(heading).step(level: 2) +/// +/// == Analysis +/// Still at #context { +/// counter(heading).display() +/// } +/// ``` +/// +/// # Page counter +/// The page counter is special. It is automatically stepped at each pagebreak. +/// But like other counters, you can also step it manually. For example, you +/// could have Roman page numbers for your preface, then switch to Arabic page +/// numbers for your main content and reset the page counter to one. +/// +/// ```example +/// >>> #set page( +/// >>> height: 100pt, +/// >>> margin: (bottom: 24pt, rest: 16pt), +/// >>> ) +/// #set page(numbering: "(i)") +/// +/// = Preface +/// The preface is numbered with +/// roman numerals. +/// +/// #set page(numbering: "1 / 1") +/// #counter(page).update(1) +/// +/// = Main text +/// Here, the counter is reset to one. +/// We also display both the current +/// page and total number of pages in +/// Arabic numbers. +/// ``` +/// +/// # Custom counters +/// To define your own counter, call the `counter` function with a string as a +/// key. This key identifies the counter globally. +/// +/// ```example +/// #let mine = counter("mycounter") +/// #context mine.display() \ +/// #mine.step() +/// #context mine.display() \ +/// #mine.update(c => c * 3) +/// #context mine.display() +/// ``` +/// +/// # How to step +/// When you define and use a custom counter, in general, you should first step +/// the counter and then display it. This way, the stepping behaviour of a +/// counter can depend on the element it is stepped for. If you were writing a +/// counter for, let's say, theorems, your theorem's definition would thus first +/// include the counter step and only then display the counter and the theorem's +/// contents. +/// +/// ```example +/// #let c = counter("theorem") +/// #let theorem(it) = block[ +/// #c.step() +/// *Theorem #context c.display():* +/// #it +/// ] +/// +/// #theorem[$1 = 1$] +/// #theorem[$2 < 3$] +/// ``` +/// +/// The rationale behind this is best explained on the example of the heading +/// counter: An update to the heading counter depends on the heading's level. By +/// stepping directly before the heading, we can correctly step from `1` to +/// `1.1` when encountering a level 2 heading. If we were to step after the +/// heading, we wouldn't know what to step to. +/// +/// Because counters should always be stepped before the elements they count, +/// they always start at zero. This way, they are at one for the first display +/// (which happens after the first step). +/// +/// # Time travel +/// Counters can travel through time! You can find out the final value of the +/// counter before it is reached and even determine what the value was at any +/// particular location in the document. +/// +/// ```example +/// #let mine = counter("mycounter") +/// +/// = Values +/// #context [ +/// Value here: #mine.get() \ +/// At intro: #mine.at(<intro>) \ +/// Final value: #mine.final() +/// ] +/// +/// #mine.update(n => n + 3) +/// +/// = Introduction <intro> +/// #lorem(10) +/// +/// #mine.step() +/// #mine.step() +/// ``` +/// +/// # Other kinds of state { #other-state } +/// The `counter` type is closely related to [state] type. Read its +/// documentation for more details on state management in Typst and why it +/// doesn't just use normal variables for counters. +#[ty(scope)] +#[derive(Debug, Clone, PartialEq, Hash)] +pub struct Counter(CounterKey); + +impl Counter { + /// Create a new counter identified by a key. + pub fn new(key: CounterKey) -> Counter { + Self(key) + } + + /// The counter for the given element. + pub fn of(func: Element) -> Self { + Self::new(CounterKey::Selector(Selector::Elem(func, None))) + } + + /// Gets the current and final value of the state combined in one state. + pub fn both( + &self, + engine: &mut Engine, + location: Location, + ) -> SourceResult<CounterState> { + let sequence = self.sequence(engine)?; + let offset = engine.introspector.query_count_before(&self.selector(), location); + let (mut at_state, at_page) = sequence[offset].clone(); + let (mut final_state, final_page) = sequence.last().unwrap().clone(); + if self.is_page() { + let at_delta = + engine.introspector.page(location).get().saturating_sub(at_page.get()); + at_state.step(NonZeroUsize::ONE, at_delta); + let final_delta = + engine.introspector.pages().get().saturating_sub(final_page.get()); + final_state.step(NonZeroUsize::ONE, final_delta); + } + Ok(CounterState(smallvec![at_state.first(), final_state.first()])) + } + + /// Gets the value of the counter at the given location. Always returns an + /// array of integers, even if the counter has just one number. + pub fn at_loc( + &self, + engine: &mut Engine, + location: Location, + ) -> SourceResult<CounterState> { + let sequence = self.sequence(engine)?; + let offset = engine.introspector.query_count_before(&self.selector(), location); + let (mut state, page) = sequence[offset].clone(); + if self.is_page() { + let delta = + engine.introspector.page(location).get().saturating_sub(page.get()); + state.step(NonZeroUsize::ONE, delta); + } + Ok(state) + } + + /// Displays the value of the counter at the given location. + pub fn display_at_loc( + &self, + engine: &mut Engine, + loc: Location, + styles: StyleChain, + numbering: &Numbering, + ) -> SourceResult<Content> { + let context = Context::new(Some(loc), Some(styles)); + Ok(self + .at_loc(engine, loc)? + .display(engine, context.track(), numbering)? + .display()) + } + + /// Produce the whole sequence of counter states. + /// + /// This has to happen just once for all counters, cutting down the number + /// of counter updates from quadratic to linear. + fn sequence( + &self, + engine: &mut Engine, + ) -> SourceResult<EcoVec<(CounterState, NonZeroUsize)>> { + self.sequence_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + ) + } + + /// Memoized implementation of `sequence`. + #[comemo::memoize] + fn sequence_impl( + &self, + routines: &Routines, + world: Tracked<dyn World + '_>, + introspector: Tracked<Introspector>, + traced: Tracked<Traced>, + sink: TrackedMut<Sink>, + route: Tracked<Route>, + ) -> SourceResult<EcoVec<(CounterState, NonZeroUsize)>> { + let mut engine = Engine { + routines, + world, + introspector, + traced, + sink, + route: Route::extend(route).unnested(), + }; + + let mut state = CounterState::init(matches!(self.0, CounterKey::Page)); + let mut page = NonZeroUsize::ONE; + let mut stops = eco_vec![(state.clone(), page)]; + + for elem in introspector.query(&self.selector()) { + if self.is_page() { + let prev = page; + page = introspector.page(elem.location().unwrap()); + + let delta = page.get() - prev.get(); + if delta > 0 { + state.step(NonZeroUsize::ONE, delta); + } + } + + if let Some(update) = match elem.with::<dyn Count>() { + Some(countable) => countable.update(), + None => Some(CounterUpdate::Step(NonZeroUsize::ONE)), + } { + state.update(&mut engine, update)?; + } + + stops.push((state.clone(), page)); + } + + Ok(stops) + } + + /// The selector relevant for this counter's updates. + fn selector(&self) -> Selector { + let mut selector = select_where!(CounterUpdateElem, Key => self.0.clone()); + + if let CounterKey::Selector(key) = &self.0 { + selector = Selector::Or(eco_vec![selector, key.clone()]); + } + + selector + } + + /// Whether this is the page counter. + fn is_page(&self) -> bool { + self.0 == CounterKey::Page + } + + /// Shared implementation of displaying between `counter.display` and + /// `DisplayElem`, which will be deprecated. + fn display_impl( + &self, + engine: &mut Engine, + location: Location, + numbering: Smart<Numbering>, + both: bool, + styles: Option<StyleChain>, + ) -> SourceResult<Value> { + let numbering = numbering + .custom() + .or_else(|| { + let styles = styles?; + let CounterKey::Selector(Selector::Elem(func, _)) = self.0 else { + return None; + }; + + if func == HeadingElem::elem() { + HeadingElem::numbering_in(styles).clone() + } else if func == FigureElem::elem() { + FigureElem::numbering_in(styles).clone() + } else if func == EquationElem::elem() { + EquationElem::numbering_in(styles).clone() + } else if func == FootnoteElem::elem() { + Some(FootnoteElem::numbering_in(styles).clone()) + } else { + None + } + }) + .unwrap_or_else(|| NumberingPattern::from_str("1.1").unwrap().into()); + + let state = if both { + self.both(engine, location)? + } else { + self.at_loc(engine, location)? + }; + + let context = Context::new(Some(location), styles); + state.display(engine, context.track(), &numbering) + } +} + +#[scope] +impl Counter { + /// Create a new counter identified by a key. + #[func(constructor)] + pub fn construct( + /// The key that identifies this counter. + /// + /// - If it is a string, creates a custom counter that is only affected + /// by manual updates, + /// - If it is the [`page`] function, counts through pages, + /// - If it is a [selector], counts through elements that matches with the + /// selector. For example, + /// - provide an element function: counts elements of that type, + /// - provide a [`{<label>}`]($label): counts elements with that label. + key: CounterKey, + ) -> Counter { + Self::new(key) + } + + /// Retrieves the value of the counter at the current location. Always + /// returns an array of integers, even if the counter has just one number. + /// + /// This is equivalent to `{counter.at(here())}`. + #[func(contextual)] + pub fn get( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + ) -> SourceResult<CounterState> { + let loc = context.location().at(span)?; + self.at_loc(engine, loc) + } + + /// Displays the current value of the counter with a numbering and returns + /// the formatted output. + /// + /// _Compatibility:_ For compatibility with Typst 0.10 and lower, this + /// function also works without an established context. Then, it will create + /// opaque contextual content rather than directly returning the output of + /// the numbering. This behaviour will be removed in a future release. + #[func(contextual)] + pub fn display( + self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The call span of the display. + span: Span, + /// A [numbering pattern or a function]($numbering), which specifies how + /// to display the counter. If given a function, that function receives + /// each number of the counter as a separate argument. If the amount of + /// numbers varies, e.g. for the heading argument, you can use an + /// [argument sink]($arguments). + /// + /// If this is omitted or set to `{auto}`, displays the counter with the + /// numbering style for the counted element or with the pattern + /// `{"1.1"}` if no such style exists. + #[default] + numbering: Smart<Numbering>, + /// If enabled, displays the current and final top-level count together. + /// Both can be styled through a single numbering pattern. This is used + /// by the page numbering property to display the current and total + /// number of pages when a pattern like `{"1 / 1"}` is given. + #[named] + #[default(false)] + both: bool, + ) -> SourceResult<Value> { + if let Ok(loc) = context.location() { + self.display_impl(engine, loc, numbering, both, context.styles().ok()) + } else { + engine.sink.warn(warning!( + span, "`counter.display` without context is deprecated"; + hint: "use it in a `context` expression instead" + )); + + Ok(CounterDisplayElem::new(self, numbering, both) + .pack() + .spanned(span) + .into_value()) + } + } + + /// Retrieves the value of the counter at the given location. Always returns + /// an array of integers, even if the counter has just one number. + /// + /// The `selector` must match exactly one element in the document. The most + /// useful kinds of selectors for this are [labels]($label) and + /// [locations]($location). + /// + /// _Compatibility:_ For compatibility with Typst 0.10 and lower, this + /// function also works without a known context if the `selector` is a + /// location. This behaviour will be removed in a future release. + #[func(contextual)] + pub fn at( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + /// The place at which the counter's value should be retrieved. + selector: LocatableSelector, + ) -> SourceResult<CounterState> { + let loc = selector.resolve_unique(engine.introspector, context).at(span)?; + self.at_loc(engine, loc) + } + + /// Retrieves the value of the counter at the end of the document. Always + /// returns an array of integers, even if the counter has just one number. + #[func(contextual)] + pub fn final_( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + /// _Compatibility:_ This argument is deprecated. It only exists for + /// compatibility with Typst 0.10 and lower and shouldn't be used + /// anymore. + #[default] + location: Option<Location>, + ) -> SourceResult<CounterState> { + if location.is_none() { + context.location().at(span)?; + } else { + engine.sink.warn(warning!( + span, "calling `counter.final` with a location is deprecated"; + hint: "try removing the location argument" + )); + } + + let sequence = self.sequence(engine)?; + let (mut state, page) = sequence.last().unwrap().clone(); + if self.is_page() { + let delta = engine.introspector.pages().get().saturating_sub(page.get()); + state.step(NonZeroUsize::ONE, delta); + } + Ok(state) + } + + /// Increases the value of the counter by one. + /// + /// The update will be in effect at the position where the returned content + /// is inserted into the document. If you don't put the output into the + /// document, nothing happens! This would be the case, for example, if you + /// write `{let _ = counter(page).step()}`. Counter updates are always + /// applied in layout order and in that case, Typst wouldn't know when to + /// step the counter. + #[func] + pub fn step( + self, + /// The call span of the update. + span: Span, + /// The depth at which to step the counter. Defaults to `{1}`. + #[named] + #[default(NonZeroUsize::ONE)] + level: NonZeroUsize, + ) -> Content { + self.update(span, CounterUpdate::Step(level)) + } + + /// Updates the value of the counter. + /// + /// Just like with `step`, the update only occurs if you put the resulting + /// content into the document. + #[func] + pub fn update( + self, + /// The call span of the update. + span: Span, + /// If given an integer or array of integers, sets the counter to that + /// value. If given a function, that function receives the previous + /// counter value (with each number as a separate argument) and has to + /// return the new value (integer or array). + update: CounterUpdate, + ) -> Content { + CounterUpdateElem::new(self.0, update).pack().spanned(span) + } +} + +impl Repr for Counter { + fn repr(&self) -> EcoString { + eco_format!("counter({})", self.0.repr()) + } +} + +/// Identifies a counter. +#[derive(Debug, Clone, PartialEq, Hash)] +pub enum CounterKey { + /// The page counter. + Page, + /// Counts elements matching the given selectors. Only works for + /// [locatable]($location/#locatable) + /// elements or labels. + Selector(Selector), + /// Counts through manual counters with the same key. + Str(Str), +} + +cast! { + CounterKey, + self => match self { + Self::Page => PageElem::elem().into_value(), + Self::Selector(v) => v.into_value(), + Self::Str(v) => v.into_value(), + }, + v: Str => Self::Str(v), + v: Label => Self::Selector(Selector::Label(v)), + v: Element => { + if v == PageElem::elem() { + Self::Page + } else { + Self::Selector(LocatableSelector::from_value(v.into_value())?.0) + } + }, + v: LocatableSelector => Self::Selector(v.0), +} + +impl Repr for CounterKey { + fn repr(&self) -> EcoString { + match self { + Self::Page => "page".into(), + Self::Selector(selector) => selector.repr(), + Self::Str(str) => str.repr(), + } + } +} + +/// An update to perform on a counter. +#[derive(Debug, Clone, PartialEq, Hash)] +pub enum CounterUpdate { + /// Set the counter to the specified state. + Set(CounterState), + /// Increase the number for the given level by one. + Step(NonZeroUsize), + /// Apply the given function to the counter's state. + Func(Func), +} + +cast! { + CounterUpdate, + v: CounterState => Self::Set(v), + v: Func => Self::Func(v), +} + +/// Elements that have special counting behaviour. +pub trait Count { + /// Get the counter update for this element. + fn update(&self) -> Option<CounterUpdate>; +} + +/// Counts through elements with different levels. +#[derive(Debug, Clone, PartialEq, Hash)] +pub struct CounterState(pub SmallVec<[usize; 3]>); + +impl CounterState { + /// Get the initial counter state for the key. + pub fn init(page: bool) -> Self { + // Special case, because pages always start at one. + Self(smallvec![usize::from(page)]) + } + + /// Advance the counter and return the numbers for the given heading. + pub fn update( + &mut self, + engine: &mut Engine, + update: CounterUpdate, + ) -> SourceResult<()> { + match update { + CounterUpdate::Set(state) => *self = state, + CounterUpdate::Step(level) => self.step(level, 1), + CounterUpdate::Func(func) => { + *self = func + .call(engine, Context::none().track(), self.0.iter().copied())? + .cast() + .at(func.span())? + } + } + Ok(()) + } + + /// Advance the number of the given level by the specified amount. + pub fn step(&mut self, level: NonZeroUsize, by: usize) { + let level = level.get(); + + while self.0.len() < level { + self.0.push(0); + } + + self.0[level - 1] = self.0[level - 1].saturating_add(by); + self.0.truncate(level); + } + + /// Get the first number of the state. + pub fn first(&self) -> usize { + self.0.first().copied().unwrap_or(1) + } + + /// Display the counter state with a numbering. + pub fn display( + &self, + engine: &mut Engine, + context: Tracked<Context>, + numbering: &Numbering, + ) -> SourceResult<Value> { + numbering.apply(engine, context, &self.0) + } +} + +cast! { + CounterState, + self => Value::Array(self.0.into_iter().map(IntoValue::into_value).collect()), + num: usize => Self(smallvec![num]), + array: Array => Self(array + .into_iter() + .map(Value::cast) + .collect::<HintedStrResult<_>>()?), +} + +/// Executes an update of a counter. +#[elem(Construct, Locatable, Show, Count)] +struct CounterUpdateElem { + /// The key that identifies the counter. + #[required] + key: CounterKey, + + /// The update to perform on the counter. + #[required] + #[internal] + update: CounterUpdate, +} + +impl Construct for CounterUpdateElem { + fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> { + bail!(args.span, "cannot be constructed manually"); + } +} + +impl Show for Packed<CounterUpdateElem> { + fn show(&self, _: &mut Engine, _: StyleChain) -> SourceResult<Content> { + Ok(Content::empty()) + } +} + +impl Count for Packed<CounterUpdateElem> { + fn update(&self) -> Option<CounterUpdate> { + Some(self.update.clone()) + } +} + +/// Executes a display of a counter. +/// +/// **Deprecation planned.** +#[elem(Construct, Locatable, Show)] +pub struct CounterDisplayElem { + /// The counter. + #[required] + #[internal] + counter: Counter, + + /// The numbering to display the counter with. + #[required] + #[internal] + numbering: Smart<Numbering>, + + /// Whether to display both the current and final value. + #[required] + #[internal] + both: bool, +} + +impl Construct for CounterDisplayElem { + fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> { + bail!(args.span, "cannot be constructed manually"); + } +} + +impl Show for Packed<CounterDisplayElem> { + #[typst_macros::time(name = "counter.display", span = self.span())] + fn show(&self, engine: &mut Engine, styles: StyleChain) -> SourceResult<Content> { + Ok(self + .counter + .display_impl( + engine, + self.location().unwrap(), + self.numbering.clone(), + self.both, + Some(styles), + )? + .display()) + } +} + +/// An specialized handler of the page counter that tracks both the physical +/// and the logical page counter. +#[derive(Debug, Copy, Clone, Eq, PartialEq, Hash)] +pub struct ManualPageCounter { + physical: NonZeroUsize, + logical: usize, +} + +impl ManualPageCounter { + /// Create a new fast page counter, starting at 1. + pub fn new() -> Self { + Self { physical: NonZeroUsize::ONE, logical: 1 } + } + + /// Get the current physical page counter state. + pub fn physical(&self) -> NonZeroUsize { + self.physical + } + + /// Get the current logical page counter state. + pub fn logical(&self) -> usize { + self.logical + } + + /// Advance past a page. + pub fn visit(&mut self, engine: &mut Engine, page: &Frame) -> SourceResult<()> { + for (_, item) in page.items() { + match item { + FrameItem::Group(group) => self.visit(engine, &group.frame)?, + FrameItem::Tag(Tag::Start(elem)) => { + let Some(elem) = elem.to_packed::<CounterUpdateElem>() else { + continue; + }; + if *elem.key() == CounterKey::Page { + let mut state = CounterState(smallvec![self.logical]); + state.update(engine, elem.update.clone())?; + self.logical = state.first(); + } + } + _ => {} + } + } + + Ok(()) + } + + /// Step past a page _boundary._ + pub fn step(&mut self) { + self.physical = self.physical.saturating_add(1); + self.logical += 1; + } +} + +impl Default for ManualPageCounter { + fn default() -> Self { + Self::new() + } +} diff --git a/crates/typst-library/src/introspection/here.rs b/crates/typst-library/src/introspection/here.rs new file mode 100644 index 00000000..9d613381 --- /dev/null +++ b/crates/typst-library/src/introspection/here.rs @@ -0,0 +1,52 @@ +use comemo::Tracked; + +use crate::diag::HintedStrResult; +use crate::foundations::{func, Context}; +use crate::introspection::Location; + +/// Provides the current location in the document. +/// +/// You can think of `here` as a low-level building block that directly extracts +/// the current location from the active [context]. Some other functions use it +/// internally: For instance, `{counter.get()}` is equivalent to +/// `{counter.at(here())}`. +/// +/// Within show rules on [locatable]($location/#locatable) elements, `{here()}` +/// will match the location of the shown element. +/// +/// If you want to display the current page number, refer to the documentation +/// of the [`counter`] type. While `here` can be used to determine the physical +/// page number, typically you want the logical page number that may, for +/// instance, have been reset after a preface. +/// +/// # Examples +/// Determining the current position in the document in combination with the +/// [`position`]($location.position) method: +/// ```example +/// #context [ +/// I am located at +/// #here().position() +/// ] +/// ``` +/// +/// Running a [query] for elements before the current position: +/// ```example +/// = Introduction +/// = Background +/// +/// There are +/// #context query( +/// selector(heading).before(here()) +/// ).len() +/// headings before me. +/// +/// = Conclusion +/// ``` +/// Refer to the [`selector`] type for more details on before/after selectors. +#[func(contextual)] +pub fn here( + /// The callsite context. + context: Tracked<Context>, +) -> HintedStrResult<Location> { + context.location() +} diff --git a/crates/typst-library/src/introspection/introspector.rs b/crates/typst-library/src/introspection/introspector.rs new file mode 100644 index 00000000..f4eaea30 --- /dev/null +++ b/crates/typst-library/src/introspection/introspector.rs @@ -0,0 +1,453 @@ +use std::collections::{BTreeSet, HashMap, HashSet}; +use std::fmt::{self, Debug, Formatter}; +use std::hash::Hash; +use std::num::NonZeroUsize; +use std::sync::RwLock; + +use ecow::EcoVec; +use smallvec::SmallVec; +use typst_utils::NonZeroExt; + +use crate::diag::{bail, StrResult}; +use crate::foundations::{Content, Label, Repr, Selector}; +use crate::introspection::{Location, Tag}; +use crate::layout::{Frame, FrameItem, Page, Point, Position, Transform}; +use crate::model::Numbering; + +/// Can be queried for elements and their positions. +#[derive(Default, Clone)] +pub struct Introspector { + /// The number of pages in the document. + pages: usize, + /// The page numberings, indexed by page number minus 1. + page_numberings: Vec<Option<Numbering>>, + + /// All introspectable elements. + elems: Vec<Pair>, + /// Lists all elements with a specific hash key. This is used for + /// introspector-assisted location assignment during measurement. + keys: MultiMap<u128, Location>, + + /// Accelerates lookup of elements by location. + locations: HashMap<Location, usize>, + /// Accelerates lookup of elements by label. + labels: MultiMap<Label, usize>, + + /// Caches queries done on the introspector. This is important because + /// even if all top-level queries are distinct, they often have shared + /// subqueries. Example: Individual counter queries with `before` that + /// all depend on a global counter query. + queries: QueryCache, +} + +/// A pair of content and its position. +type Pair = (Content, Position); + +impl Introspector { + /// Creates an introspector for a page list. + #[typst_macros::time(name = "introspect")] + pub fn new(pages: &[Page]) -> Self { + IntrospectorBuilder::new().build(pages) + } + + /// Iterates over all locatable elements. + pub fn all(&self) -> impl Iterator<Item = &Content> + '_ { + self.elems.iter().map(|(c, _)| c) + } + + /// Retrieves the element with the given index. + #[track_caller] + fn get_by_idx(&self, idx: usize) -> &Content { + &self.elems[idx].0 + } + + /// Retrieves the position of the element with the given index. + #[track_caller] + fn get_pos_by_idx(&self, idx: usize) -> Position { + self.elems[idx].1 + } + + /// Retrieves an element by its location. + fn get_by_loc(&self, location: &Location) -> Option<&Content> { + self.locations.get(location).map(|&idx| self.get_by_idx(idx)) + } + + /// Retrieves the position of the element with the given index. + fn get_pos_by_loc(&self, location: &Location) -> Option<Position> { + self.locations.get(location).map(|&idx| self.get_pos_by_idx(idx)) + } + + /// Performs a binary search for `elem` among the `list`. + fn binary_search(&self, list: &[Content], elem: &Content) -> Result<usize, usize> { + list.binary_search_by_key(&self.elem_index(elem), |elem| self.elem_index(elem)) + } + + /// Gets the index of this element. + fn elem_index(&self, elem: &Content) -> usize { + self.loc_index(&elem.location().unwrap()) + } + + /// Gets the index of the element with this location among all. + fn loc_index(&self, location: &Location) -> usize { + self.locations.get(location).copied().unwrap_or(usize::MAX) + } +} + +#[comemo::track] +impl Introspector { + /// Query for all matching elements. + pub fn query(&self, selector: &Selector) -> EcoVec<Content> { + let hash = typst_utils::hash128(selector); + if let Some(output) = self.queries.get(hash) { + return output; + } + + let output = match selector { + Selector::Elem(..) => self + .all() + .filter(|elem| selector.matches(elem, None)) + .cloned() + .collect(), + Selector::Location(location) => { + self.get_by_loc(location).cloned().into_iter().collect() + } + Selector::Label(label) => self + .labels + .get(label) + .iter() + .map(|&idx| self.get_by_idx(idx).clone()) + .collect(), + Selector::Or(selectors) => selectors + .iter() + .flat_map(|sel| self.query(sel)) + .map(|elem| self.elem_index(&elem)) + .collect::<BTreeSet<usize>>() + .into_iter() + .map(|idx| self.get_by_idx(idx).clone()) + .collect(), + Selector::And(selectors) => { + let mut results: Vec<_> = + selectors.iter().map(|sel| self.query(sel)).collect(); + + // Extract the smallest result list and then keep only those + // elements in the smallest list that are also in all other + // lists. + results + .iter() + .enumerate() + .min_by_key(|(_, vec)| vec.len()) + .map(|(i, _)| i) + .map(|i| results.swap_remove(i)) + .iter() + .flatten() + .filter(|candidate| { + results + .iter() + .all(|other| self.binary_search(other, candidate).is_ok()) + }) + .cloned() + .collect() + } + Selector::Before { selector, end, inclusive } => { + let mut list = self.query(selector); + if let Some(end) = self.query_first(end) { + // Determine which elements are before `end`. + let split = match self.binary_search(&list, &end) { + // Element itself is contained. + Ok(i) => i + *inclusive as usize, + // Element itself is not contained. + Err(i) => i, + }; + list = list[..split].into(); + } + list + } + Selector::After { selector, start, inclusive } => { + let mut list = self.query(selector); + if let Some(start) = self.query_first(start) { + // Determine which elements are after `start`. + let split = match self.binary_search(&list, &start) { + // Element itself is contained. + Ok(i) => i + !*inclusive as usize, + // Element itself is not contained. + Err(i) => i, + }; + list = list[split..].into(); + } + list + } + // Not supported here. + Selector::Can(_) | Selector::Regex(_) => EcoVec::new(), + }; + + self.queries.insert(hash, output.clone()); + output + } + + /// Query for the first element that matches the selector. + pub fn query_first(&self, selector: &Selector) -> Option<Content> { + match selector { + Selector::Location(location) => self.get_by_loc(location).cloned(), + Selector::Label(label) => self + .labels + .get(label) + .first() + .map(|&idx| self.get_by_idx(idx).clone()), + _ => self.query(selector).first().cloned(), + } + } + + /// Query for the first element that matches the selector. + pub fn query_unique(&self, selector: &Selector) -> StrResult<Content> { + match selector { + Selector::Location(location) => self + .get_by_loc(location) + .cloned() + .ok_or_else(|| "element does not exist in the document".into()), + Selector::Label(label) => self.query_label(*label).cloned(), + _ => { + let elems = self.query(selector); + if elems.len() > 1 { + bail!("selector matches multiple elements",); + } + elems + .into_iter() + .next() + .ok_or_else(|| "selector does not match any element".into()) + } + } + } + + /// Query for a unique element with the label. + pub fn query_label(&self, label: Label) -> StrResult<&Content> { + match *self.labels.get(&label) { + [idx] => Ok(self.get_by_idx(idx)), + [] => bail!("label `{}` does not exist in the document", label.repr()), + _ => bail!("label `{}` occurs multiple times in the document", label.repr()), + } + } + + /// This is an optimized version of + /// `query(selector.before(end, true).len()` used by counters and state. + pub fn query_count_before(&self, selector: &Selector, end: Location) -> usize { + // See `query()` for details. + let list = self.query(selector); + if let Some(end) = self.get_by_loc(&end) { + match self.binary_search(&list, end) { + Ok(i) => i + 1, + Err(i) => i, + } + } else { + list.len() + } + } + + /// The total number pages. + pub fn pages(&self) -> NonZeroUsize { + NonZeroUsize::new(self.pages).unwrap_or(NonZeroUsize::ONE) + } + + /// Find the page number for the given location. + pub fn page(&self, location: Location) -> NonZeroUsize { + self.position(location).page + } + + /// Find the position for the given location. + pub fn position(&self, location: Location) -> Position { + self.get_pos_by_loc(&location) + .unwrap_or(Position { page: NonZeroUsize::ONE, point: Point::zero() }) + } + + /// Gets the page numbering for the given location, if any. + pub fn page_numbering(&self, location: Location) -> Option<&Numbering> { + let page = self.page(location); + self.page_numberings + .get(page.get() - 1) + .and_then(|slot| slot.as_ref()) + } + + /// Try to find a location for an element with the given `key` hash + /// that is closest after the `anchor`. + /// + /// This is used for introspector-assisted location assignment during + /// measurement. See the "Dealing with Measurement" section of the + /// [`Locator`](crate::introspection::Locator) docs for more details. + pub fn locator(&self, key: u128, anchor: Location) -> Option<Location> { + let anchor = self.loc_index(&anchor); + self.keys + .get(&key) + .iter() + .copied() + .min_by_key(|loc| self.loc_index(loc).wrapping_sub(anchor)) + } +} + +impl Debug for Introspector { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + f.pad("Introspector(..)") + } +} + +/// A map from one keys to multiple elements. +#[derive(Clone)] +struct MultiMap<K, V>(HashMap<K, SmallVec<[V; 1]>>); + +impl<K, V> MultiMap<K, V> +where + K: Hash + Eq, +{ + fn get(&self, key: &K) -> &[V] { + self.0.get(key).map_or(&[], |vec| vec.as_slice()) + } + + fn insert(&mut self, key: K, value: V) { + self.0.entry(key).or_default().push(value); + } + + fn take(&mut self, key: &K) -> Option<impl Iterator<Item = V>> { + self.0.remove(key).map(|vec| vec.into_iter()) + } +} + +impl<K, V> Default for MultiMap<K, V> { + fn default() -> Self { + Self(HashMap::new()) + } +} + +/// Caches queries. +#[derive(Default)] +struct QueryCache(RwLock<HashMap<u128, EcoVec<Content>>>); + +impl QueryCache { + fn get(&self, hash: u128) -> Option<EcoVec<Content>> { + self.0.read().unwrap().get(&hash).cloned() + } + + fn insert(&self, hash: u128, output: EcoVec<Content>) { + self.0.write().unwrap().insert(hash, output); + } +} + +impl Clone for QueryCache { + fn clone(&self) -> Self { + Self(RwLock::new(self.0.read().unwrap().clone())) + } +} + +/// Builds the introspector. +#[derive(Default)] +struct IntrospectorBuilder { + page_numberings: Vec<Option<Numbering>>, + seen: HashSet<Location>, + insertions: MultiMap<Location, Vec<Pair>>, + keys: MultiMap<u128, Location>, + locations: HashMap<Location, usize>, + labels: MultiMap<Label, usize>, +} + +impl IntrospectorBuilder { + /// Create an empty builder. + fn new() -> Self { + Self::default() + } + + /// Build the introspector. + fn build(mut self, pages: &[Page]) -> Introspector { + self.page_numberings.reserve(pages.len()); + + // Discover all elements. + let mut root = Vec::new(); + for (i, page) in pages.iter().enumerate() { + self.page_numberings.push(page.numbering.clone()); + self.discover( + &mut root, + &page.frame, + NonZeroUsize::new(1 + i).unwrap(), + Transform::identity(), + ); + } + + self.locations.reserve(self.seen.len()); + + // Save all pairs and their descendants in the correct order. + let mut elems = Vec::with_capacity(self.seen.len()); + for pair in root { + self.visit(&mut elems, pair); + } + + Introspector { + pages: pages.len(), + page_numberings: self.page_numberings, + elems, + keys: self.keys, + locations: self.locations, + labels: self.labels, + queries: QueryCache::default(), + } + } + + /// Processes the tags in the frame. + fn discover( + &mut self, + sink: &mut Vec<Pair>, + frame: &Frame, + page: NonZeroUsize, + ts: Transform, + ) { + for (pos, item) in frame.items() { + match item { + FrameItem::Group(group) => { + let ts = ts + .pre_concat(Transform::translate(pos.x, pos.y)) + .pre_concat(group.transform); + + if let Some(parent) = group.parent { + let mut nested = vec![]; + self.discover(&mut nested, &group.frame, page, ts); + self.insertions.insert(parent, nested); + } else { + self.discover(sink, &group.frame, page, ts); + } + } + FrameItem::Tag(Tag::Start(elem)) => { + let loc = elem.location().unwrap(); + if self.seen.insert(loc) { + let point = pos.transform(ts); + sink.push((elem.clone(), Position { page, point })); + } + } + FrameItem::Tag(Tag::End(loc, key)) => { + self.keys.insert(*key, *loc); + } + _ => {} + } + } + } + + /// Saves a pair and all its descendants into `elems` and populates the + /// acceleration structures. + fn visit(&mut self, elems: &mut Vec<Pair>, pair: Pair) { + let elem = &pair.0; + let loc = elem.location().unwrap(); + let idx = elems.len(); + + // Populate the location acceleration map. + self.locations.insert(loc, idx); + + // Populate the label acceleration map. + if let Some(label) = elem.label() { + self.labels.insert(label, idx); + } + + // Save the element. + elems.push(pair); + + // Process potential descendants. + if let Some(insertions) = self.insertions.take(&loc) { + for pair in insertions.flatten() { + self.visit(elems, pair); + } + } + } +} diff --git a/crates/typst-library/src/introspection/locate.rs b/crates/typst-library/src/introspection/locate.rs new file mode 100644 index 00000000..9a0e28e2 --- /dev/null +++ b/crates/typst-library/src/introspection/locate.rs @@ -0,0 +1,119 @@ +use comemo::{Track, Tracked}; +use typst_syntax::Span; + +use crate::diag::{warning, HintedStrResult, SourceResult}; +use crate::engine::Engine; +use crate::foundations::{ + cast, elem, func, Content, Context, Func, LocatableSelector, NativeElement, Packed, + Show, StyleChain, Value, +}; +use crate::introspection::{Locatable, Location}; + +/// Determines the location of an element in the document. +/// +/// Takes a selector that must match exactly one element and returns that +/// element's [`location`]. This location can, in particular, be used to +/// retrieve the physical [`page`]($location.page) number and +/// [`position`]($location.position) (page, x, y) for that element. +/// +/// # Examples +/// Locating a specific element: +/// ```example +/// #context [ +/// Introduction is at: \ +/// #locate(<intro>).position() +/// ] +/// +/// = Introduction <intro> +/// ``` +/// +/// # Compatibility +/// In Typst 0.10 and lower, the `locate` function took a closure that made the +/// current location in the document available (like [`here`] does now). This +/// usage pattern is deprecated. Compatibility with the old way will remain for +/// a while to give package authors time to upgrade. To that effect, `locate` +/// detects whether it received a selector or a user-defined function and +/// adjusts its semantics accordingly. This behaviour will be removed in the +/// future. +#[func(contextual)] +pub fn locate( + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The span of the `locate` call. + span: Span, + /// A selector that should match exactly one element. This element will be + /// located. + /// + /// Especially useful in combination with + /// - [`here`] to locate the current context, + /// - a [`location`] retrieved from some queried element via the + /// [`location()`]($content.location) method on content. + selector: LocateInput, +) -> HintedStrResult<LocateOutput> { + Ok(match selector { + LocateInput::Selector(selector) => { + LocateOutput::Location(selector.resolve_unique(engine.introspector, context)?) + } + LocateInput::Func(func) => { + engine.sink.warn(warning!( + span, "`locate` with callback function is deprecated"; + hint: "use a `context` expression instead" + )); + + LocateOutput::Content(LocateElem::new(func).pack().spanned(span)) + } + }) +} + +/// Compatible input type. +pub enum LocateInput { + Selector(LocatableSelector), + Func(Func), +} + +cast! { + LocateInput, + v: Func => { + if v.element().is_some() { + Self::Selector(Value::Func(v).cast()?) + } else { + Self::Func(v) + } + }, + v: LocatableSelector => Self::Selector(v), +} + +/// Compatible output type. +pub enum LocateOutput { + Location(Location), + Content(Content), +} + +cast! { + LocateOutput, + self => match self { + Self::Location(v) => v.into_value(), + Self::Content(v) => v.into_value(), + }, + v: Location => Self::Location(v), + v: Content => Self::Content(v), +} + +/// Executes a `locate` call. +#[elem(Locatable, Show)] +struct LocateElem { + /// The function to call with the location. + #[required] + func: Func, +} + +impl Show for Packed<LocateElem> { + #[typst_macros::time(name = "locate", span = self.span())] + fn show(&self, engine: &mut Engine, styles: StyleChain) -> SourceResult<Content> { + let location = self.location().unwrap(); + let context = Context::new(Some(location), Some(styles)); + Ok(self.func().call(engine, context.track(), [location])?.display()) + } +} diff --git a/crates/typst-library/src/introspection/location.rs b/crates/typst-library/src/introspection/location.rs new file mode 100644 index 00000000..8f4caaec --- /dev/null +++ b/crates/typst-library/src/introspection/location.rs @@ -0,0 +1,113 @@ +use std::fmt::{self, Debug, Formatter}; +use std::num::NonZeroUsize; + +use ecow::EcoString; + +use crate::engine::Engine; +use crate::foundations::{func, scope, ty, Repr}; +use crate::layout::Position; +use crate::model::Numbering; + +/// Identifies an element in the document. +/// +/// A location uniquely identifies an element in the document and lets you +/// access its absolute position on the pages. You can retrieve the current +/// location with the [`here`] function and the location of a queried or shown +/// element with the [`location()`]($content.location) method on content. +/// +/// # Locatable elements { #locatable } +/// Currently, only a subset of element functions is locatable. Aside from +/// headings and figures, this includes equations, references, quotes and all +/// elements with an explicit label. As a result, you _can_ query for e.g. +/// [`strong`] elements, but you will find only those that have an explicit +/// label attached to them. This limitation will be resolved in the future. +#[ty(scope)] +#[derive(Copy, Clone, Eq, PartialEq, Hash)] +pub struct Location(u128); + +impl Location { + /// Create a new location from a unique hash. + pub fn new(hash: u128) -> Self { + Self(hash) + } + + /// Extract the raw hash. + pub fn hash(self) -> u128 { + self.0 + } + + /// Produces a well-known variant of this location. + /// + /// This is a synthetic location created from another one and is used, for + /// example, in bibliography management to create individual linkable + /// locations for reference entries from the bibliography's location. + pub fn variant(self, n: usize) -> Self { + Self(typst_utils::hash128(&(self.0, n))) + } +} + +#[scope] +impl Location { + /// Returns the page number for this location. + /// + /// Note that this does not return the value of the [page counter]($counter) + /// at this location, but the true page number (starting from one). + /// + /// If you want to know the value of the page counter, use + /// `{counter(page).at(loc)}` instead. + /// + /// Can be used with [`here`] to retrieve the physical page position + /// of the current context: + /// ```example + /// #context [ + /// I am located on + /// page #here().page() + /// ] + /// ``` + #[func] + pub fn page(self, engine: &mut Engine) -> NonZeroUsize { + engine.introspector.page(self) + } + + /// Returns a dictionary with the page number and the x, y position for this + /// location. The page number starts at one and the coordinates are measured + /// from the top-left of the page. + /// + /// If you only need the page number, use `page()` instead as it allows + /// Typst to skip unnecessary work. + #[func] + pub fn position(self, engine: &mut Engine) -> Position { + engine.introspector.position(self) + } + + /// Returns the page numbering pattern of the page at this location. This + /// can be used when displaying the page counter in order to obtain the + /// local numbering. This is useful if you are building custom indices or + /// outlines. + /// + /// If the page numbering is set to `{none}` at that location, this function + /// returns `{none}`. + #[func] + pub fn page_numbering(self, engine: &mut Engine) -> Option<Numbering> { + engine.introspector.page_numbering(self).cloned() + } +} + +impl Debug for Location { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "Location({})", self.0) + } +} + +impl Repr for Location { + fn repr(&self) -> EcoString { + "..".into() + } +} + +/// Makes this element as locatable through the introspector. +pub trait Locatable {} + +/// Marks this element as not being queryable even though it is locatable for +/// internal reasons. +pub trait Unqueriable {} diff --git a/crates/typst-library/src/introspection/locator.rs b/crates/typst-library/src/introspection/locator.rs new file mode 100644 index 00000000..4045aa9c --- /dev/null +++ b/crates/typst-library/src/introspection/locator.rs @@ -0,0 +1,350 @@ +use std::collections::HashMap; +use std::fmt::{self, Debug, Formatter}; +use std::hash::Hash; +use std::sync::OnceLock; + +use comemo::{Tracked, Validate}; + +use crate::introspection::{Introspector, Location}; + +/// Provides locations for elements in the document. +/// +/// A [`Location`] is a unique ID for an element generated during realization. +/// +/// # How to use this +/// The same content may yield different results when laid out in different +/// parts of the document. To reflect this, every layout operation receives a +/// locator and every layout operation requires a locator. In code: +/// +/// - all layouters receive an owned `Locator` +/// - all layout functions take an owned `Locator` +/// +/// When a layouter only requires a single sublayout call, it can simply pass on +/// its locator. When a layouter needs to call multiple sublayouters, we need to +/// make an explicit decision: +/// +/// - Split: When we're layouting multiple distinct children (or other pieces of +/// content), we need to split up the locator with [`Locator::split`]. This +/// allows us to produce multiple new `Locator`s for the sublayouts. When we +/// split the locator, each sublocator will be a distinct entity and using it +/// to e.g. layout the same piece of figure content will yield distinctly +/// numbered figures. +/// +/// - Relayout: When we're layouting the same content multiple times (e.g. when +/// measuring something), we can call [`Locator::relayout`] to use the same +/// locator multiple times. This indicates to the compiler that it's actually +/// the same content. Using it to e.g. layout the same piece of figure content +/// will yield the same figure number both times. Typically, when we layout +/// something multiple times using `relayout`, only one of the outputs +/// actually ends up in the document, while the other outputs are only used +/// for measurement and then discarded. +/// +/// The `Locator` intentionally does not implement `Copy` and `Clone` so that it +/// can only be used once. This ensures that whenever we are layouting multiple +/// things, we make an explicit decision whether we want to split or relayout. +/// +/// # How it works +/// There are two primary considerations for the assignment of locations: +/// +/// 1. Locations should match up over multiple layout iterations, so that +/// elements can be identified as being the same: That's the whole point of +/// them. +/// +/// 2. Locations should be as stable as possible across document edits, so that +/// incremental compilation is effective. +/// +/// 3. We want to assign them with as little long-lived state as possible to +/// enable parallelization of the layout process. +/// +/// Let's look at a few different assignment strategies to get a feeling for +/// these requirements: +/// +/// - A very simple way to generate unique IDs would be to just increase a +/// counter for each element. In this setup, (1) is somewhat satisfied: In +/// principle, the counter will line up across iterations, but things start to +/// break down once we generate content dependent on introspection since the +/// IDs generated for that new content will shift the IDs for all following +/// elements in the document. (2) is not satisfied since an edit in the middle +/// of the document shifts all later IDs. (3) is obviously not satisfied. +/// Conclusion: Not great. +/// +/// - To make things more robust, we can incorporate some stable knowledge about +/// the element into the ID. For this, we can use the element's span since it +/// is already mostly unique: Elements resulting from different source code +/// locations are guaranteed to have different spans. However, we can also +/// have multiple distinct elements generated from the same source location: +/// e.g. `#for _ in range(5) { figure(..) }`. To handle this case, we can then +/// disambiguate elements with the same span with an increasing counter. In +/// this setup, (1) is mostly satisfied: Unless we do stuff like generating +/// colliding counter updates dependent on introspection, things will line up. +/// (2) is also reasonably well satisfied, as typical edits will only affect +/// the single element at the currently edited span. Only if we edit inside of +/// a function, loop, or similar construct, we will affect multiple elements. +/// (3) is still a problem though, since we count up. +/// +/// - What's left is to get rid of the mutable state. Note that layout is a +/// recursive process and has a tree-shaped execution graph. Thus, we can try +/// to determine an element's ID based on the path of execution taken in this +/// graph. Something like "3rd element in layer 1, 7th element in layer 2, +/// ..". This is basically the first approach, but on a per-layer basis. Thus, +/// we can again apply our trick from the second approach, and use the span + +/// disambiguation strategy on a per-layer basis: "1st element with span X in +/// layer 1, 3rd element with span Y in layer 2". The chance for a collision +/// is now pretty low and our state is wholly local to each level. So, if we +/// want to parallelize layout within a layer, we can generate the IDs for +/// that layer upfront and then start forking out. The final remaining +/// question is how we can compactly encode this information: For this, as +/// always, we use hashing! We incorporate the ID information from each layer +/// into a single hash and thanks to the collision resistance of 128-bit +/// SipHash, we get almost guaranteed unique locations. We don't even store +/// the full layer information at all, but rather hash _hierarchically:_ Let +/// `k_x` be our local per-layer ID for layer `x` and `h_x` be the full +/// combined hash for layer `x`. We compute `h_n = hash(h_(n-1), k_n)`. +/// +/// So that's what's going on conceptually in this type. For efficient +/// memoization, we do all of this in a tracked fashion, such that we only +/// observe the hash for all the layers above us, if we actually need to +/// generate a [`Location`]. Thus, if we have a piece of content that does not +/// contain any locatable elements, we can cache its layout even if it occurs in +/// different places. +/// +/// # Dealing with measurement +/// As explained above, any kind of measurement the compiler performs requires a +/// locator that matches the one used during real layout. This ensures that the +/// locations assigned during measurement match up exactly with the locations of +/// real document elements. Without this guarantee, many introspection-driven +/// features (like counters, state, and citations) don't work correctly (since +/// they perform queries dependent on concrete locations). +/// +/// This is all fine and good, but things get really tricky when the _user_ +/// measures such introspecting content since the user isn't kindly managing +/// locators for us. Our standard `Locator` workflow assigns locations that +/// depend a lot on the exact placement in the hierarchy of elements. For this +/// reason, something that is measured, but then placed into something like a +/// grid will get a location influenced by the grid. Without a locator, we can't +/// make the connection between the measured content and the real content, so we +/// can't ensure that the locations match up. +/// +/// One possible way to deal with this is to force the user to uniquely identify +/// content before being measured after all. This would mean that the user needs +/// to come up with an identifier that is unique within the surrounding context +/// block and attach it to the content in some way. However, after careful +/// consideration, I have concluded that this is simply too big of an ask from +/// users: Understanding why this is even necessary is pretty complicated and +/// how to best come up with a unique ID is even more so. +/// +/// For this reason, I chose an alternative best-effort approach: The locator +/// has a custom "measurement mode" (entered through [`LocatorLink::measure`]), +/// in which it does its best to assign locations that match up. Specifically, +/// it uses the key hashes of the individual locatable elements in the measured +/// content (which may not be unique if content is reused) and combines them +/// with the context's location to find the most likely matching real element. +/// This approach works correctly almost all of the time (especially for +/// "normal" hand-written content where the key hashes rarely collide, as +/// opposed to code-heavy things where they do). +/// +/// Support for enhancing this with user-provided uniqueness can still be added +/// in the future. It will most likely anyway be added simply because it's +/// automatically included when we add a way to "freeze" content for things like +/// slidehows. But it will be opt-in because it's just too much complication. +pub struct Locator<'a> { + /// A local hash that incorporates all layers since the last memoization + /// boundary. + local: u128, + /// A pointer to an outer cached locator, which contributes the information + /// for all the layers beyond the memoization boundary on-demand. + outer: Option<&'a LocatorLink<'a>>, +} + +impl<'a> Locator<'a> { + /// Create a new root-level locator. + /// + /// Should typically only be created at the document level, though there + /// are a few places where we use it as well that just don't support + /// introspection (e.g. drawable patterns). + pub fn root() -> Self { + Self { local: 0, outer: None } + } + + /// Creates a new synthetic locator. + /// + /// This can be used to create a new dependent layout based on an element. + /// This is used for layouting footnote entries based on the location + /// of the associated footnote. + pub fn synthesize(location: Location) -> Self { + Self { local: location.hash(), outer: None } + } + + /// Creates a new locator that points to the given link. + pub fn link(link: &'a LocatorLink<'a>) -> Self { + Self { local: 0, outer: Some(link) } + } +} + +impl<'a> Locator<'a> { + /// Returns a type that can be used to generate `Locator`s for multiple + /// child elements. See the type-level docs for more details. + pub fn split(self) -> SplitLocator<'a> { + SplitLocator { + local: self.local, + outer: self.outer, + disambiguators: HashMap::new(), + } + } + + /// Creates a copy of this locator for measurement or relayout of the same + /// content. See the type-level docs for more details. + /// + /// This is effectively just `Clone`, but the `Locator` doesn't implement + /// `Clone` to make this operation explicit. + pub fn relayout(&self) -> Self { + Self { local: self.local, outer: self.outer } + } +} + +#[comemo::track] +impl<'a> Locator<'a> { + /// Resolves the locator based on its local and the outer information. + fn resolve(&self) -> Resolved { + match self.outer { + None => Resolved::Hash(self.local), + Some(outer) => match outer.resolve() { + Resolved::Hash(outer) => { + Resolved::Hash(typst_utils::hash128(&(self.local, outer))) + } + Resolved::Measure(anchor) => Resolved::Measure(anchor), + }, + } + } +} + +impl Debug for Locator<'_> { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + write!(f, "Locator({:?})", self.resolve()) + } +} + +/// The fully resolved value of a locator. +#[derive(Debug, Copy, Clone, Hash)] +enum Resolved { + /// The full hash, incorporating the local and all outer information. + Hash(u128), + /// Indicates that the locator is in measurement mode, with the given anchor + /// location. + Measure(Location), +} + +/// A type that generates unique sublocators. +pub struct SplitLocator<'a> { + /// A local hash that incorporates all layers since the last memoization + /// boundary. + local: u128, + /// A pointer to an outer cached locator, which contributes the information + /// for all the layers beyond the memoization boundary on-demand. + outer: Option<&'a LocatorLink<'a>>, + /// Simply counts up the number of times we've seen each local hash. + disambiguators: HashMap<u128, usize>, +} + +impl<'a> SplitLocator<'a> { + /// Produces a sublocator for a subtree keyed by `key`. The keys do *not* + /// need to be unique among the `next()` calls on this split locator. (They + /// can even all be `&()`.) + /// + /// However, stable & mostly unique keys lead to more stable locations + /// throughout edits, improving incremental compilation performance. + /// + /// A common choice for a key is the span of the content that will be + /// layouted with this locator. + pub fn next<K: Hash>(&mut self, key: &K) -> Locator<'a> { + self.next_inner(typst_utils::hash128(key)) + } + + /// Produces a sublocator for a subtree. + pub fn next_inner(&mut self, key: u128) -> Locator<'a> { + // Produce a locator disambiguator, for elements with the same key + // within this `SplitLocator`. + let disambiguator = { + let slot = self.disambiguators.entry(key).or_default(); + std::mem::replace(slot, *slot + 1) + }; + + // Combine the key, disambiguator and local hash into a sub-local hash. + // The outer information is not yet merged into this, it is added + // on-demand in `Locator::resolve`. + let local = typst_utils::hash128(&(key, disambiguator, self.local)); + + Locator { outer: self.outer, local } + } + + /// Produces a unique location for an element. + pub fn next_location( + &mut self, + introspector: Tracked<Introspector>, + key: u128, + ) -> Location { + match self.next_inner(key).resolve() { + Resolved::Hash(hash) => Location::new(hash), + Resolved::Measure(anchor) => { + // If we aren't able to find a matching element in the document, + // default to the anchor, so that it's at least remotely in + // the right area (so that counters can be resolved). + introspector.locator(key, anchor).unwrap_or(anchor) + } + } + } +} + +/// A locator can be linked to this type to only access information across the +/// memoization boundary on-demand, improving the cache hit chance. +pub struct LocatorLink<'a> { + /// The link itself. + kind: LinkKind<'a>, + /// The cached resolved link. + resolved: OnceLock<Resolved>, +} + +/// The different kinds of locator links. +enum LinkKind<'a> { + /// An outer `Locator`, which we can resolved if necessary. + /// + /// We need to override the constraint's lifetime here so that `Tracked` is + /// covariant over the constraint. If it becomes invariant, we're in for a + /// world of lifetime pain. + Outer(Tracked<'a, Locator<'a>, <Locator<'static> as Validate>::Constraint>), + /// A link which indicates that we are in measurement mode. + Measure(Location), +} + +impl<'a> LocatorLink<'a> { + /// Create a locator link. + pub fn new(outer: Tracked<'a, Locator<'a>>) -> Self { + LocatorLink { + kind: LinkKind::Outer(outer), + resolved: OnceLock::new(), + } + } + + /// Creates a link that puts any linked downstream locator into measurement + /// mode. + /// + /// Read the "Dealing with measurement" section of the [`Locator`] docs for + /// more details. + pub fn measure(anchor: Location) -> Self { + LocatorLink { + kind: LinkKind::Measure(anchor), + resolved: OnceLock::new(), + } + } + + /// Resolve the link. + /// + /// The result is cached in this link, so that we don't traverse the link + /// chain over and over again. + fn resolve(&self) -> Resolved { + *self.resolved.get_or_init(|| match self.kind { + LinkKind::Outer(outer) => outer.resolve(), + LinkKind::Measure(anchor) => Resolved::Measure(anchor), + }) + } +} diff --git a/crates/typst-library/src/introspection/metadata.rs b/crates/typst-library/src/introspection/metadata.rs new file mode 100644 index 00000000..06000174 --- /dev/null +++ b/crates/typst-library/src/introspection/metadata.rs @@ -0,0 +1,38 @@ +use crate::diag::SourceResult; +use crate::engine::Engine; +use crate::foundations::{elem, Content, Packed, Show, StyleChain, Value}; +use crate::introspection::Locatable; + +/// Exposes a value to the query system without producing visible content. +/// +/// This element can be retrieved with the [`query`] function and from the +/// command line with +/// [`typst query`]($reference/introspection/query/#command-line-queries). Its +/// purpose is to expose an arbitrary value to the introspection system. To +/// identify a metadata value among others, you can attach a [`label`] to it and +/// query for that label. +/// +/// The `metadata` element is especially useful for command line queries because +/// it allows you to expose arbitrary values to the outside world. +/// +/// ```example +/// // Put metadata somewhere. +/// #metadata("This is a note") <note> +/// +/// // And find it from anywhere else. +/// #context { +/// query(<note>).first().value +/// } +/// ``` +#[elem(Show, Locatable)] +pub struct MetadataElem { + /// The value to embed into the document. + #[required] + pub value: Value, +} + +impl Show for Packed<MetadataElem> { + fn show(&self, _: &mut Engine, _styles: StyleChain) -> SourceResult<Content> { + Ok(Content::empty()) + } +} diff --git a/crates/typst-library/src/introspection/mod.rs b/crates/typst-library/src/introspection/mod.rs new file mode 100644 index 00000000..b1ff2e08 --- /dev/null +++ b/crates/typst-library/src/introspection/mod.rs @@ -0,0 +1,53 @@ +//! Interaction between document parts. + +mod counter; +#[path = "here.rs"] +mod here_; +mod introspector; +#[path = "locate.rs"] +mod locate_; +mod location; +mod locator; +mod metadata; +#[path = "query.rs"] +mod query_; +mod state; +mod tag; + +pub use self::counter::*; +pub use self::here_::*; +pub use self::introspector::*; +pub use self::locate_::*; +pub use self::location::*; +pub use self::locator::*; +pub use self::metadata::*; +pub use self::query_::*; +pub use self::state::*; +pub use self::tag::*; + +use crate::foundations::{category, Category, Scope}; + +/// Interactions between document parts. +/// +/// This category is home to Typst's introspection capabilities: With the +/// `counter` function, you can access and manipulate page, section, figure, and +/// equation counters or create custom ones. Meanwhile, the `query` function +/// lets you search for elements in the document to construct things like a list +/// of figures or headers which show the current chapter title. +/// +/// Most of the functions are _contextual._ It is recommended to read the chapter +/// on [context] before continuing here. +#[category] +pub static INTROSPECTION: Category; + +/// Hook up all `introspection` definitions. +pub fn define(global: &mut Scope) { + global.category(INTROSPECTION); + global.define_type::<Location>(); + global.define_type::<Counter>(); + global.define_type::<State>(); + global.define_elem::<MetadataElem>(); + global.define_func::<here>(); + global.define_func::<query>(); + global.define_func::<locate>(); +} diff --git a/crates/typst-library/src/introspection/query.rs b/crates/typst-library/src/introspection/query.rs new file mode 100644 index 00000000..7b106bf0 --- /dev/null +++ b/crates/typst-library/src/introspection/query.rs @@ -0,0 +1,171 @@ +use comemo::Tracked; +use typst_syntax::Span; + +use crate::diag::{warning, HintedStrResult}; +use crate::engine::Engine; +use crate::foundations::{func, Array, Context, LocatableSelector, Value}; +use crate::introspection::Location; + +/// Finds elements in the document. +/// +/// The `query` functions lets you search your document for elements of a +/// particular type or with a particular label. To use it, you first need to +/// ensure that [context] is available. +/// + +/// # Finding elements +/// In the example below, we manually create a table of contents instead of +/// using the [`outline`] function. +/// +/// To do this, we first query for all headings in the document at level 1 and +/// where `outlined` is true. Querying only for headings at level 1 ensures +/// that, for the purpose of this example, sub-headings are not included in the +/// table of contents. The `outlined` field is used to exclude the "Table of +/// Contents" heading itself. +/// +/// Note that we open a `context` to be able to use the `query` function. +/// +/// ```example +/// >>> #set page( +/// >>> width: 240pt, +/// >>> height: 180pt, +/// >>> margin: (top: 20pt, bottom: 35pt) +/// >>> ) +/// #set page(numbering: "1") +/// +/// #heading(outlined: false)[ +/// Table of Contents +/// ] +/// #context { +/// let chapters = query( +/// heading.where( +/// level: 1, +/// outlined: true, +/// ) +/// ) +/// for chapter in chapters { +/// let loc = chapter.location() +/// let nr = numbering( +/// loc.page-numbering(), +/// ..counter(page).at(loc), +/// ) +/// [#chapter.body #h(1fr) #nr \ ] +/// } +/// } +/// +/// = Introduction +/// #lorem(10) +/// #pagebreak() +/// +/// == Sub-Heading +/// #lorem(8) +/// +/// = Discussion +/// #lorem(18) +/// ``` +/// +/// To get the page numbers, we first get the location of the elements returned +/// by `query` with [`location`]($content.location). We then also retrieve the +/// [page numbering]($location.page-numbering) and [page +/// counter]($counter/#page-counter) at that location and apply the numbering to +/// the counter. +/// +/// # A word of caution { #caution } +/// To resolve all your queries, Typst evaluates and layouts parts of the +/// document multiple times. However, there is no guarantee that your queries +/// can actually be completely resolved. If you aren't careful a query can +/// affect itself—leading to a result that never stabilizes. +/// +/// In the example below, we query for all headings in the document. We then +/// generate as many headings. In the beginning, there's just one heading, +/// titled `Real`. Thus, `count` is `1` and one `Fake` heading is generated. +/// Typst sees that the query's result has changed and processes it again. This +/// time, `count` is `2` and two `Fake` headings are generated. This goes on and +/// on. As we can see, the output has a finite amount of headings. This is +/// because Typst simply gives up after a few attempts. +/// +/// In general, you should try not to write queries that affect themselves. The +/// same words of caution also apply to other introspection features like +/// [counters]($counter) and [state]. +/// +/// ```example +/// = Real +/// #context { +/// let elems = query(heading) +/// let count = elems.len() +/// count * [= Fake] +/// } +/// ``` +/// +/// # Command line queries +/// You can also perform queries from the command line with the `typst query` +/// command. This command executes an arbitrary query on the document and +/// returns the resulting elements in serialized form. Consider the following +/// `example.typ` file which contains some invisible [metadata]: +/// +/// ```typ +/// #metadata("This is a note") <note> +/// ``` +/// +/// You can execute a query on it as follows using Typst's CLI: +/// ```sh +/// $ typst query example.typ "<note>" +/// [ +/// { +/// "func": "metadata", +/// "value": "This is a note", +/// "label": "<note>" +/// } +/// ] +/// ``` +/// +/// Frequently, you're interested in only one specific field of the resulting +/// elements. In the case of the `metadata` element, the `value` field is the +/// interesting one. You can extract just this field with the `--field` +/// argument. +/// +/// ```sh +/// $ typst query example.typ "<note>" --field value +/// ["This is a note"] +/// ``` +/// +/// If you are interested in just a single element, you can use the `--one` +/// flag to extract just it. +/// +/// ```sh +/// $ typst query example.typ "<note>" --field value --one +/// "This is a note" +/// ``` +#[func(contextual)] +pub fn query( + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The span of the `query` call. + span: Span, + /// Can be + /// - an element function like a `heading` or `figure`, + /// - a `{<label>}`, + /// - a more complex selector like `{heading.where(level: 1)}`, + /// - or `{selector(heading).before(here())}`. + /// + /// Only [locatable]($location/#locatable) element functions are supported. + target: LocatableSelector, + /// _Compatibility:_ This argument is deprecated. It only exists for + /// compatibility with Typst 0.10 and lower and shouldn't be used anymore. + #[default] + location: Option<Location>, +) -> HintedStrResult<Array> { + if location.is_none() { + context.introspect()?; + } else { + engine.sink.warn(warning!( + span, "calling `query` with a location is deprecated"; + hint: "try removing the location argument" + )); + } + + let vec = engine.introspector.query(&target.0); + Ok(vec.into_iter().map(Value::Content).collect()) +} diff --git a/crates/typst-library/src/introspection/state.rs b/crates/typst-library/src/introspection/state.rs new file mode 100644 index 00000000..13c96b50 --- /dev/null +++ b/crates/typst-library/src/introspection/state.rs @@ -0,0 +1,476 @@ +use comemo::{Track, Tracked, TrackedMut}; +use ecow::{eco_format, eco_vec, EcoString, EcoVec}; +use typst_syntax::Span; + +use crate::diag::{bail, warning, At, SourceResult}; +use crate::engine::{Engine, Route, Sink, Traced}; +use crate::foundations::{ + cast, elem, func, scope, select_where, ty, Args, Construct, Content, Context, Func, + LocatableSelector, NativeElement, Packed, Repr, Selector, Show, Str, StyleChain, + Value, +}; +use crate::introspection::{Introspector, Locatable, Location}; +use crate::routines::Routines; +use crate::World; + +/// Manages stateful parts of your document. +/// +/// Let's say you have some computations in your document and want to remember +/// the result of your last computation to use it in the next one. You might try +/// something similar to the code below and expect it to output 10, 13, 26, and +/// 21. However this **does not work** in Typst. If you test this code, you will +/// see that Typst complains with the following error message: _Variables from +/// outside the function are read-only and cannot be modified._ +/// +/// ```typ +/// // This doesn't work! +/// #let x = 0 +/// #let compute(expr) = { +/// x = eval( +/// expr.replace("x", str(x)) +/// ) +/// [New value is #x. ] +/// } +/// +/// #compute("10") \ +/// #compute("x + 3") \ +/// #compute("x * 2") \ +/// #compute("x - 5") +/// ``` +/// +/// # State and document markup { #state-and-markup } +/// Why does it do that? Because, in general, this kind of computation with side +/// effects is problematic in document markup and Typst is upfront about that. +/// For the results to make sense, the computation must proceed in the same +/// order in which the results will be laid out in the document. In our simple +/// example, that's the case, but in general it might not be. +/// +/// Let's look at a slightly different, but similar kind of state: The heading +/// numbering. We want to increase the heading counter at each heading. Easy +/// enough, right? Just add one. Well, it's not that simple. Consider the +/// following example: +/// +/// ```example +/// #set heading(numbering: "1.") +/// #let template(body) = [ +/// = Outline +/// ... +/// #body +/// ] +/// +/// #show: template +/// +/// = Introduction +/// ... +/// ``` +/// +/// Here, Typst first processes the body of the document after the show rule, +/// sees the `Introduction` heading, then passes the resulting content to the +/// `template` function and only then sees the `Outline`. Just counting up would +/// number the `Introduction` with `1` and the `Outline` with `2`. +/// +/// # Managing state in Typst { #state-in-typst } +/// So what do we do instead? We use Typst's state management system. Calling +/// the `state` function with an identifying string key and an optional initial +/// value gives you a state value which exposes a few functions. The two most +/// important ones are `get` and `update`: +/// +/// - The [`get`]($state.get) function retrieves the current value of the state. +/// Because the value can vary over the course of the document, it is a +/// _contextual_ function that can only be used when [context]($context) is +/// available. +/// +/// - The [`update`]($state.update) function modifies the state. You can give it +/// any value. If given a non-function value, it sets the state to that value. +/// If given a function, that function receives the previous state and has to +/// return the new state. +/// +/// Our initial example would now look like this: +/// +/// ```example +/// #let s = state("x", 0) +/// #let compute(expr) = [ +/// #s.update(x => +/// eval(expr.replace("x", str(x))) +/// ) +/// New value is #context s.get(). +/// ] +/// +/// #compute("10") \ +/// #compute("x + 3") \ +/// #compute("x * 2") \ +/// #compute("x - 5") +/// ``` +/// +/// State managed by Typst is always updated in layout order, not in evaluation +/// order. The `update` method returns content and its effect occurs at the +/// position where the returned content is inserted into the document. +/// +/// As a result, we can now also store some of the computations in variables, +/// but they still show the correct results: +/// +/// ```example +/// >>> #let s = state("x", 0) +/// >>> #let compute(expr) = [ +/// >>> #s.update(x => +/// >>> eval(expr.replace("x", str(x))) +/// >>> ) +/// >>> New value is #context s.get(). +/// >>> ] +/// <<< ... +/// +/// #let more = [ +/// #compute("x * 2") \ +/// #compute("x - 5") +/// ] +/// +/// #compute("10") \ +/// #compute("x + 3") \ +/// #more +/// ``` +/// +/// This example is of course a bit silly, but in practice this is often exactly +/// what you want! A good example are heading counters, which is why Typst's +/// [counting system]($counter) is very similar to its state system. +/// +/// # Time Travel +/// By using Typst's state management system you also get time travel +/// capabilities! We can find out what the value of the state will be at any +/// position in the document from anywhere else. In particular, the `at` method +/// gives us the value of the state at any particular location and the `final` +/// methods gives us the value of the state at the end of the document. +/// +/// ```example +/// >>> #let s = state("x", 0) +/// >>> #let compute(expr) = [ +/// >>> #s.update(x => { +/// >>> eval(expr.replace("x", str(x))) +/// >>> }) +/// >>> New value is #context s.get(). +/// >>> ] +/// <<< ... +/// +/// Value at `<here>` is +/// #context s.at(<here>) +/// +/// #compute("10") \ +/// #compute("x + 3") \ +/// *Here.* <here> \ +/// #compute("x * 2") \ +/// #compute("x - 5") +/// ``` +/// +/// # A word of caution { #caution } +/// To resolve the values of all states, Typst evaluates parts of your code +/// multiple times. However, there is no guarantee that your state manipulation +/// can actually be completely resolved. +/// +/// For instance, if you generate state updates depending on the final value of +/// a state, the results might never converge. The example below illustrates +/// this. We initialize our state with `1` and then update it to its own final +/// value plus 1. So it should be `2`, but then its final value is `2`, so it +/// should be `3`, and so on. This example displays a finite value because Typst +/// simply gives up after a few attempts. +/// +/// ```example +/// // This is bad! +/// #let s = state("x", 1) +/// #context s.update(s.final() + 1) +/// #context s.get() +/// ``` +/// +/// In general, you should try not to generate state updates from within context +/// expressions. If possible, try to express your updates as non-contextual +/// values or functions that compute the new value from the previous value. +/// Sometimes, it cannot be helped, but in those cases it is up to you to ensure +/// that the result converges. +#[ty(scope)] +#[derive(Debug, Clone, PartialEq, Hash)] +pub struct State { + /// The key that identifies the state. + key: Str, + /// The initial value of the state. + init: Value, +} + +impl State { + /// Create a new state identified by a key. + pub fn new(key: Str, init: Value) -> State { + Self { key, init } + } + + /// Get the value of the state at the given location. + pub fn at_loc(&self, engine: &mut Engine, loc: Location) -> SourceResult<Value> { + let sequence = self.sequence(engine)?; + let offset = engine.introspector.query_count_before(&self.selector(), loc); + Ok(sequence[offset].clone()) + } + + /// Produce the whole sequence of states. + /// + /// This has to happen just once for all states, cutting down the number + /// of state updates from quadratic to linear. + fn sequence(&self, engine: &mut Engine) -> SourceResult<EcoVec<Value>> { + self.sequence_impl( + engine.routines, + engine.world, + engine.introspector, + engine.traced, + TrackedMut::reborrow_mut(&mut engine.sink), + engine.route.track(), + ) + } + + /// Memoized implementation of `sequence`. + #[comemo::memoize] + fn sequence_impl( + &self, + routines: &Routines, + world: Tracked<dyn World + '_>, + introspector: Tracked<Introspector>, + traced: Tracked<Traced>, + sink: TrackedMut<Sink>, + route: Tracked<Route>, + ) -> SourceResult<EcoVec<Value>> { + let mut engine = Engine { + routines, + world, + introspector, + traced, + sink, + route: Route::extend(route).unnested(), + }; + let mut state = self.init.clone(); + let mut stops = eco_vec![state.clone()]; + + for elem in introspector.query(&self.selector()) { + let elem = elem.to_packed::<StateUpdateElem>().unwrap(); + match elem.update() { + StateUpdate::Set(value) => state = value.clone(), + StateUpdate::Func(func) => { + state = func.call(&mut engine, Context::none().track(), [state])? + } + } + stops.push(state.clone()); + } + + Ok(stops) + } + + /// The selector for this state's updates. + fn selector(&self) -> Selector { + select_where!(StateUpdateElem, Key => self.key.clone()) + } +} + +#[scope] +impl State { + /// Create a new state identified by a key. + #[func(constructor)] + pub fn construct( + /// The key that identifies this state. + key: Str, + /// The initial value of the state. + #[default] + init: Value, + ) -> State { + Self::new(key, init) + } + + /// Retrieves the value of the state at the current location. + /// + /// This is equivalent to `{state.at(here())}`. + #[func(contextual)] + pub fn get( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + ) -> SourceResult<Value> { + let loc = context.location().at(span)?; + self.at_loc(engine, loc) + } + + /// Retrieves the value of the state at the given selector's unique match. + /// + /// The `selector` must match exactly one element in the document. The most + /// useful kinds of selectors for this are [labels]($label) and + /// [locations]($location). + /// + /// _Compatibility:_ For compatibility with Typst 0.10 and lower, this + /// function also works without a known context if the `selector` is a + /// location. This behaviour will be removed in a future release. + #[func(contextual)] + pub fn at( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + /// The place at which the state's value should be retrieved. + selector: LocatableSelector, + ) -> SourceResult<Value> { + let loc = selector.resolve_unique(engine.introspector, context).at(span)?; + self.at_loc(engine, loc) + } + + /// Retrieves the value of the state at the end of the document. + #[func(contextual)] + pub fn final_( + &self, + /// The engine. + engine: &mut Engine, + /// The callsite context. + context: Tracked<Context>, + /// The callsite span. + span: Span, + /// _Compatibility:_ This argument is deprecated. It only exists for + /// compatibility with Typst 0.10 and lower and shouldn't be used + /// anymore. + #[default] + location: Option<Location>, + ) -> SourceResult<Value> { + if location.is_none() { + context.location().at(span)?; + } else { + engine.sink.warn(warning!( + span, "calling `state.final` with a location is deprecated"; + hint: "try removing the location argument" + )); + } + + let sequence = self.sequence(engine)?; + Ok(sequence.last().unwrap().clone()) + } + + /// Update the value of the state. + /// + /// The update will be in effect at the position where the returned content + /// is inserted into the document. If you don't put the output into the + /// document, nothing happens! This would be the case, for example, if you + /// write `{let _ = state("key").update(7)}`. State updates are always + /// applied in layout order and in that case, Typst wouldn't know when to + /// update the state. + #[func] + pub fn update( + self, + /// The span of the `update` call. + span: Span, + /// If given a non function-value, sets the state to that value. If + /// given a function, that function receives the previous state and has + /// to return the new state. + update: StateUpdate, + ) -> Content { + StateUpdateElem::new(self.key, update).pack().spanned(span) + } + + /// Displays the current value of the state. + /// + /// **Deprecation planned:** Use [`get`]($state.get) instead. + #[func] + pub fn display( + self, + /// The engine. + engine: &mut Engine, + /// The span of the `display` call. + span: Span, + /// A function which receives the value of the state and can return + /// arbitrary content which is then displayed. If this is omitted, the + /// value is directly displayed. + #[default] + func: Option<Func>, + ) -> Content { + engine.sink.warn(warning!( + span, "`state.display` is deprecated"; + hint: "use `state.get` in a `context` expression instead" + )); + + StateDisplayElem::new(self, func).pack().spanned(span) + } +} + +impl Repr for State { + fn repr(&self) -> EcoString { + eco_format!("state({}, {})", self.key.repr(), self.init.repr()) + } +} + +/// An update to perform on a state. +#[derive(Debug, Clone, PartialEq, Hash)] +pub enum StateUpdate { + /// Set the state to the specified value. + Set(Value), + /// Apply the given function to the state. + Func(Func), +} + +cast! { + StateUpdate, + v: Func => Self::Func(v), + v: Value => Self::Set(v), +} + +/// Executes a display of a state. +#[elem(Construct, Locatable, Show)] +struct StateUpdateElem { + /// The key that identifies the state. + #[required] + key: Str, + + /// The update to perform on the state. + #[required] + #[internal] + update: StateUpdate, +} + +impl Construct for StateUpdateElem { + fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> { + bail!(args.span, "cannot be constructed manually"); + } +} + +impl Show for Packed<StateUpdateElem> { + fn show(&self, _: &mut Engine, _: StyleChain) -> SourceResult<Content> { + Ok(Content::empty()) + } +} + +/// Executes a display of a state. +/// +/// **Deprecation planned.** +#[elem(Construct, Locatable, Show)] +struct StateDisplayElem { + /// The state. + #[required] + #[internal] + state: State, + + /// The function to display the state with. + #[required] + #[internal] + func: Option<Func>, +} + +impl Show for Packed<StateDisplayElem> { + #[typst_macros::time(name = "state.display", span = self.span())] + fn show(&self, engine: &mut Engine, styles: StyleChain) -> SourceResult<Content> { + let location = self.location().unwrap(); + let context = Context::new(Some(location), Some(styles)); + let value = self.state().at_loc(engine, location)?; + Ok(match self.func() { + Some(func) => func.call(engine, context.track(), [value])?.display(), + None => value.display(), + }) + } +} + +impl Construct for StateDisplayElem { + fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> { + bail!(args.span, "cannot be constructed manually"); + } +} diff --git a/crates/typst-library/src/introspection/tag.rs b/crates/typst-library/src/introspection/tag.rs new file mode 100644 index 00000000..b2bae28e --- /dev/null +++ b/crates/typst-library/src/introspection/tag.rs @@ -0,0 +1,73 @@ +use std::fmt::{self, Debug, Formatter}; + +use crate::diag::{bail, SourceResult}; +use crate::engine::Engine; +use crate::foundations::{ + elem, Args, Construct, Content, NativeElement, Packed, Unlabellable, +}; +use crate::introspection::Location; + +/// Marks the start or end of a locatable element. +#[derive(Clone, PartialEq, Hash)] +pub enum Tag { + /// The stored element starts here. + /// + /// Content placed in a tag **must** have a [`Location`] or there will be + /// panics. + Start(Content), + /// The element with the given location and key hash ends here. + /// + /// Note: The key hash is stored here instead of in `Start` simply to make + /// the two enum variants more balanced in size, keeping a `Tag`'s memory + /// size down. There are no semantic reasons for this. + End(Location, u128), +} + +impl Tag { + /// Access the location of the tag. + pub fn location(&self) -> Location { + match self { + Tag::Start(elem) => elem.location().unwrap(), + Tag::End(loc, _) => *loc, + } + } +} + +impl Debug for Tag { + fn fmt(&self, f: &mut Formatter) -> fmt::Result { + match self { + Tag::Start(elem) => write!(f, "Start({:?})", elem.elem().name()), + Tag::End(..) => f.pad("End"), + } + } +} + +/// Holds a tag for a locatable element that was realized. +/// +/// The `TagElem` is handled by all layouters. The held element becomes +/// available for introspection in the next compiler iteration. +#[elem(Construct, Unlabellable)] +pub struct TagElem { + /// The introspectable element. + #[required] + #[internal] + pub tag: Tag, +} + +impl TagElem { + /// Create a packed tag element. + pub fn packed(tag: Tag) -> Content { + let mut content = Self::new(tag).pack(); + // We can skip preparation for the `TagElem`. + content.mark_prepared(); + content + } +} + +impl Construct for TagElem { + fn construct(_: &mut Engine, args: &mut Args) -> SourceResult<Content> { + bail!(args.span, "cannot be constructed manually") + } +} + +impl Unlabellable for Packed<TagElem> {} |