Oregami
Repositories/oxedyne/fe2o3

oxedyne/fe2o3/fe2o3_austenite/src/eval/intro.rs

50.9 KiB, 255 runs

created by r1870400018:63214, which is this file's identity for as long as the history lasts, whatever it is later renamed to

download · who wrote it · its history

1// SPDX-License-Identifier: Apache-2.0
2// Original work copyright (c) the Typst project authors (typst-library `introspection/*` and `foundations/{styles,content}.rs`, version 0.15.1).
3// Modified for Austenite: ported to Hematite's types, IR and error handling.
4// U8 owns this file: the introspector, counter and state keys, and the read log the fixpoint compares.
5// A counter or state is a fold of its update elements in document order; nothing here observes layout
6// except through the positions the pages recorded.
7//
8// A port of Typst 0.15's `Introspector`, `Counter` and `State` semantics (typst-library, Apache-2.0):
9// document order is the order the pages placed the elements' start tags, out-of-flow material being read
10// where its parent stands; a counter's value at a location is the fold of every matching update at or
11// before it; and `before`/`after` bound a query by the first match of their bound. Every question a pass
12// asks is recorded with a hash of its answer, and the pass converges when each question answers the same
13// against the introspector the pass built, as Typst's `Constraint::validate` decides.
14//
15// Streaming (addendum 2026-09-23): the introspector is the one structure that spans the document. It
16// keeps one compact record per located element -- the prepared element, its position, and its place in
17// document order -- and never a frame, a node or a page. [`Builder`] gathers the records while the pages
18// stream past, and [`Builder::finish`] orders them once, at the end of the pass.
19
20use crate::diag::DiagnosticKind;
21use crate::doc::DocInfo;
22use crate::eval::args::Args;
23use crate::eval::content::{
24 Content,
25 ElemKind,
26 FieldId,
27};
28use crate::eval::fp;
29use crate::eval::func::Func;
30use crate::driver::Recorder;
31use crate::eval::lib;
32use crate::eval::lib::model;
33use crate::eval::locate::Location;
34use crate::eval::select::Selector;
35use crate::eval::styles::{
36 error_hints,
37 StyleChain,
38};
39use crate::eval::value::{
40 Dict,
41 Label,
42 Length,
43 Value,
44};
45use crate::eval::{
46 ops,
47 Context,
48 Engine,
49};
50use crate::ir::Sp;
51use crate::ledger::{
52 Anchor,
53 Ledger,
54 Position,
55};
56use crate::syntax::Span;
57use crate::timings::Phase;
58
59use oxedyne_fe2o3_core::prelude::*;
60use oxedyne_fe2o3_hash::fingerprint::Fingerprint;
61use oxedyne_fe2o3_hash::fingerprint::Fingerprinter;
62
63use std::collections::{
64 HashMap,
65 HashSet,
66};
67use std::sync::Arc;
68
69// The introspector
70
71/// One located element: as realisation prepared it (location and synthesised fields set, its body
72/// `Arc`s shared with the module), and where the pages placed its start tag.
73#[derive(Clone, Debug)]
74pub struct Record {
75 pub elem: Content,
76 pub pos: Position,
77}
78
79/// One pass's layout facts. The records are in document order, so a record's index is its order key.
80#[derive(Clone, Debug, Default)]
81pub struct Introspector {
82 records: Vec<Record>,
83 index: HashMap<Location, u32>, // location to record
84 kinds: HashMap<ElemKind, Vec<u32>>, // records by element kind, ascending
85 labels: HashMap<Label, Vec<u32>>, // records by label, ascending
86 pages: u32,
87 numberings: Vec<(u32, Value)>, // `page.numbering` runs: first page, value
88 info: DocInfo, // the document's metadata as the last page's styles set it
89}
90
91impl Introspector {
92 /// The document's title, authors, description and keywords, as the styles in force on its last page
93 /// set them: a `set document` anywhere at the top level, or inside a template the document is shown
94 /// through. The PDF's Info dictionary is written from it.
95 pub fn info(&self) -> &DocInfo { &self.info }
96
97 pub fn len(&self) -> usize { self.records.len() }
98
99 pub fn is_empty(&self) -> bool { self.records.is_empty() }
100
101 pub fn pages(&self) -> u32 { self.pages }
102
103 /// The records in document order.
104 pub fn iter(&self) -> impl Iterator<Item = &Record> + '_ { self.records.iter() }
105
106 /// The located elements in document order.
107 pub fn elems(&self) -> impl Iterator<Item = &Content> + '_ { self.records.iter().map(|r| &r.elem) }
108
109 /// Where `loc` stands in document order.
110 pub fn order(&self, loc: Location) -> Option<usize> { self.index.get(&loc).map(|i| *i as usize) }
111
112 pub fn get(&self, loc: Location) -> Option<&Content> {
113 self.order(loc).and_then(|i| self.records.get(i)).map(|r| &r.elem)
114 }
115
116 pub fn position(&self, loc: Location) -> Option<Position> {
117 self.order(loc).and_then(|i| self.records.get(i)).map(|r| r.pos)
118 }
119
120 pub fn page(&self, loc: Location) -> Option<u32> { self.position(loc).map(|p| p.page) }
121
122 /// The `page.numbering` in force on a page, `none` for a page the pass did not lay out.
123 pub fn numbering_of_page(&self, page: u32) -> Value {
124 let n = self.numberings.partition_point(|(first, _)| *first <= page);
125 match n.checked_sub(1).and_then(|i| self.numberings.get(i)) {
126 Some((_, v)) if page >= 1 && page <= self.pages => v.clone(),
127 _ => Value::None,
128 }
129 }
130
131 /// How many runs of equal page numbering the pass had.
132 pub fn numbering_runs(&self) -> usize { self.numberings.len() }
133
134 /// The numbering of the page `loc` landed on, `none` where the page has none or `loc` was not placed.
135 pub fn page_numbering(&self, loc: Location) -> Value {
136 match self.page(loc) {
137 Some(p) => self.numbering_of_page(p),
138 None => Value::None,
139 }
140 }
141
142 pub fn query(&self, selector: &Selector) -> Outcome<Vec<Content>> {
143 let found = res!(self.query_indices(selector));
144 Ok(found.into_iter().filter_map(|i| self.records.get(i)).map(|r| r.elem.clone()).collect())
145 }
146
147 /// The first element in document order the selector matches.
148 pub fn query_first(&self, selector: &Selector) -> Outcome<Option<Content>> {
149 let first = match selector {
150 Selector::Location(l) => self.order(*l),
151 Selector::Label(l) => self.labels.get(l).and_then(|v| v.first()).map(|i| *i as usize),
152 other => res!(self.query_indices(other)).first().copied(),
153 };
154 Ok(first.and_then(|i| self.records.get(i)).map(|r| r.elem.clone()))
155 }
156
157 /// The document-order indices of the matches, ascending. An element selector reads only its kind's
158 /// records and a label only its own; `before`, `after`, `or` and `and` are answered over the matches
159 /// of their parts, which is why they never match a single element.
160 pub fn query_indices(&self, selector: &Selector) -> Outcome<Vec<usize>> {
161 match selector {
162 Selector::Location(loc) => Ok(self.order(*loc).into_iter().collect()),
163 Selector::Label(l) => Ok(self.labels.get(l).map(|v| v.iter().map(|i| *i as usize).collect())
164 .unwrap_or_default()),
165 Selector::Elem(kind, fields) => {
166 let ids = match self.kinds.get(kind) {
167 Some(v) => v,
168 None => return Ok(Vec::new()),
169 };
170 if fields.is_none() {
171 return Ok(ids.iter().map(|i| *i as usize).collect());
172 }
173 let mut out = Vec::new();
174 for i in ids {
175 if let Some(r) = self.records.get(*i as usize) {
176 if res!(selector.matches(&r.elem, None)) {
177 out.push(*i as usize);
178 }
179 }
180 }
181 Ok(out)
182 }
183 Selector::Or(ss) => {
184 let mut all = Vec::new();
185 for s in ss {
186 all.extend(res!(self.query_indices(s)));
187 }
188 all.sort_unstable();
189 all.dedup();
190 Ok(all)
191 }
192 Selector::And(ss) => {
193 let mut acc: Option<Vec<usize>> = None;
194 for s in ss {
195 let found = res!(self.query_indices(s));
196 acc = Some(match acc {
197 None => found,
198 Some(a) => {
199 let keep: HashSet<usize> = found.into_iter().collect();
200 a.into_iter().filter(|i| keep.contains(i)).collect()
201 }
202 });
203 }
204 Ok(acc.unwrap_or_default())
205 }
206 Selector::Before { selector, end, inclusive } => {
207 let mut list = res!(self.query_indices(selector));
208 if let Some(bound) = res!(self.query_indices(end)).first().copied() {
209 list.retain(|i| if *inclusive { *i <= bound } else { *i < bound });
210 }
211 Ok(list)
212 }
213 Selector::After { selector, start, inclusive } => {
214 let mut list = res!(self.query_indices(selector));
215 if let Some(bound) = res!(self.query_indices(start)).first().copied() {
216 list.retain(|i| if *inclusive { *i >= bound } else { *i > bound });
217 }
218 Ok(list)
219 }
220 // Text is never located, and `check_locatable` refuses these before a query is made.
221 Selector::Text(_) | Selector::Regex(_) => Ok(Vec::new()),
222 }
223 }
224
225 /// How many matches sit at or before `loc`. A location the pages did not place counts every match,
226 /// as Typst's does.
227 pub fn count_before(&self, selector: &Selector, loc: Location) -> Outcome<usize> {
228 let list = res!(self.query_indices(selector));
229 Ok(match self.order(loc) {
230 Some(at) => list.partition_point(|i| *i <= at),
231 None => list.len(),
232 })
233 }
234
235 /// The `.prl` ledger, derived at finish: every located element's `Location` anchor and the page count.
236 pub fn ledger(&self) -> Ledger {
237 let mut ledger = Ledger::new();
238 for r in &self.records {
239 if let Some(loc) = r.elem.location() {
240 ledger.record(Anchor::new(loc.anchor(), r.pos));
241 }
242 }
243 ledger.total_pages = self.pages;
244 ledger
245 }
246
247 /// The bytes the introspector's own tables hold, by capacity: the records, the location, kind and
248 /// label indices and the numbering runs. The elements the records point to are not counted; they are
249 /// realisation's prepared elements, whose bodies the module shares.
250 pub fn footprint(&self) -> usize {
251 use std::mem::size_of;
252 // A hash table holds its entries and one control byte each, over a power-of-two bucket count.
253 fn table<K, V>(cap: usize) -> usize {
254 if cap == 0 { 0 } else { (cap * 8 / 7).next_power_of_two() * (size_of::<(K, V)>() + 1) }
255 }
256 let mut n = self.records.capacity() * size_of::<Record>();
257 n += table::<Location, u32>(self.index.capacity());
258 n += table::<ElemKind, Vec<u32>>(self.kinds.capacity());
259 n += self.kinds.values().map(|v| v.capacity() * size_of::<u32>()).sum::<usize>();
260 n += table::<Label, Vec<u32>>(self.labels.capacity());
261 n += self.labels.values().map(|v| v.capacity() * size_of::<u32>()).sum::<usize>();
262 n += self.numberings.capacity() * size_of::<(u32, Value)>();
263 n
264 }
265}
266
267// The builder
268
269/// Where a recorded item stands before the pass is ordered: in the order the pages placed it, or under
270/// a parent, read just after the parent's own place.
271#[derive(Clone, Debug)]
272enum Item {
273 Record(Record),
274 Mark(u64),
275}
276
277/// Gathers one pass's records as the pages are placed, in the pages' order, and orders them into an
278/// [`Introspector`] at the end. Out-of-flow material (a float's body, a footnote's entry) is recorded
279/// with the id of its logical parent, the parent's location or a [`mark`](Self::mark), and is read where
280/// that parent stands, as Typst's introspector reads an insertion (U6b's `Order`, folded in here).
281#[derive(Debug, Default)]
282pub struct Builder {
283 items: Vec<(Option<u64>, Item)>, // parent, item; arrival order
284 seen: HashSet<Location>,
285 pages: u32,
286 numberings: Vec<(u32, Value)>,
287 last_hash: Option<Fingerprint>, // the hash of the latest numbering run's value
288 info: DocInfo,
289}
290
291impl Builder {
292 pub fn new() -> Self { Self::default() }
293
294 /// Records a located element's start tag where it was placed. A location placed twice (a repeated
295 /// table header) keeps its first place, as Typst's does; an element with no location records
296 /// nothing.
297 pub fn record(&mut self, elem: &Content, pos: Position, parent: Option<u64>) {
298 let loc = match elem.location() {
299 Some(l) => l,
300 None => return,
301 };
302 if self.seen.insert(loc) {
303 self.items.push((parent, Item::Record(Record { elem: elem.clone(), pos })));
304 }
305 }
306
307 /// Marks where out-of-flow material with this id logically stands.
308 pub fn mark(&mut self, id: u64) {
309 self.items.push((None, Item::Mark(id)));
310 }
311
312 /// Takes the document metadata in force on the page just placed. Each page's chain already holds every
313 /// `set document` before it, so the last page's is the document's.
314 pub fn document(&mut self, info: DocInfo) {
315 self.info = info;
316 }
317
318 /// Counts page `number` and its numbering. Runs of equal numberings are held once; a page given
319 /// twice counts once.
320 pub fn page(&mut self, number: u32, numbering: &Value) {
321 if number <= self.pages {
322 return;
323 }
324 self.pages = number;
325 let mut h = Fingerprinter::new();
326 hash_value(&mut h, numbering);
327 let h = h.finish();
328 if self.last_hash != Some(h) {
329 self.numberings.push((number, numbering.clone()));
330 self.last_hash = Some(h);
331 }
332 }
333
334 /// Orders the records into document order and builds the introspector's indices.
335 pub fn finish(self) -> Introspector {
336 let Builder { items, pages, mut numberings, info, .. } = self;
337 // A parent id that nothing marks leaves its children where they were placed, as U6b's `Order` did.
338 let mut anchored: HashSet<u64> = HashSet::new();
339 for (_, item) in &items {
340 match item {
341 Item::Mark(id) => { anchored.insert(*id); }
342 Item::Record(r) => if let Some(l) = r.elem.location() { anchored.insert(l.0); },
343 }
344 }
345 let mut top: Vec<Item> = Vec::with_capacity(items.len());
346 let mut under: HashMap<u64, Vec<Item>> = HashMap::new();
347 let mut parents: Vec<u64> = Vec::new(); // in the order their first child arrived, for leftovers
348 for (parent, item) in items {
349 match parent {
350 Some(p) if anchored.contains(&p) => {
351 let list = under.entry(p).or_default();
352 if list.is_empty() {
353 parents.push(p);
354 }
355 list.push(item);
356 }
357 _ => top.push(item),
358 }
359 }
360 let mut records = Vec::with_capacity(top.len() + under.values().map(|v| v.len()).sum::<usize>());
361 for item in top {
362 emit(item, &mut under, &mut records, 0);
363 }
364 // A parent chain that loops, or runs deeper than any real nesting, is read in arrival order.
365 for p in parents {
366 if let Some(list) = under.remove(&p) {
367 for item in list {
368 emit(item, &mut under, &mut records, 0);
369 }
370 }
371 }
372 records.shrink_to_fit();
373 numberings.shrink_to_fit();
374 let mut index = HashMap::with_capacity(records.len());
375 let mut kinds: HashMap<ElemKind, Vec<u32>> = HashMap::new();
376 let mut labels: HashMap<Label, Vec<u32>> = HashMap::new();
377 for (i, r) in records.iter().enumerate() {
378 let i = i as u32;
379 if let Some(l) = r.elem.location() {
380 index.insert(l, i);
381 }
382 if let Some(k) = r.elem.kind() {
383 kinds.entry(k).or_default().push(i);
384 }
385 if let Some(l) = r.elem.label() {
386 labels.entry(l.clone()).or_default().push(i);
387 }
388 }
389 for v in kinds.values_mut() {
390 v.shrink_to_fit();
391 }
392 for v in labels.values_mut() {
393 v.shrink_to_fit();
394 }
395 Introspector { records, index, kinds, labels, pages, numberings, info }
396 }
397}
398
399// The pages place their located elements straight into the builder.
400impl Recorder for Builder {
401 fn record(&mut self, elem: &Content, pos: Position, parent: Option<u64>) {
402 Builder::record(self, elem, pos, parent)
403 }
404
405 fn mark(&mut self, id: u64) {
406 Builder::mark(self, id)
407 }
408}
409
410/// Emits an item, then everything recorded under it, depth first.
411fn emit(item: Item, under: &mut HashMap<u64, Vec<Item>>, out: &mut Vec<Record>, depth: usize) {
412 let id = match item {
413 Item::Mark(id) => Some(id),
414 Item::Record(r) => {
415 let id = r.elem.location().map(|l| l.0);
416 out.push(r);
417 id
418 }
419 };
420 if depth >= 64 {
421 return;
422 }
423 if let Some(children) = id.and_then(|id| under.remove(&id)) {
424 for c in children {
425 emit(c, under, out, depth + 1);
426 }
427 }
428}
429
430// Counters
431
432#[derive(Clone, Debug)]
433pub enum CounterKey {
434 Page,
435 Selector(Selector), // `counter(heading)`, `counter(figure.where(kind: table))`
436 Str(String), // `counter("mine")`
437}
438
439impl CounterKey {
440 /// The key as Typst shows it in a counter update's `key` field: the element function, the string, or
441 /// the selector.
442 pub fn to_value(&self) -> Value {
443 match self {
444 CounterKey::Page => Value::Func(Func::Element(ElemKind::Page)),
445 CounterKey::Str(s) => Value::str(s.clone()),
446 CounterKey::Selector(Selector::Elem(k, None)) => Value::Func(Func::Element(*k)),
447 CounterKey::Selector(Selector::Label(l)) => Value::Label(l.clone()),
448 CounterKey::Selector(Selector::Location(l)) => Value::Location(*l),
449 CounterKey::Selector(s) => Value::Selector(Arc::new(s.clone())),
450 }
451 }
452
453 /// The key a stored `key` field names; `None` for a value no counter could have been made from.
454 pub fn from_value(v: &Value) -> Option<CounterKey> {
455 match v {
456 Value::Func(f) => match f.element() {
457 Some(ElemKind::Page) => Some(CounterKey::Page),
458 Some(k) => Some(CounterKey::Selector(Selector::Elem(k, None))),
459 None => None,
460 },
461 Value::Str(s) => Some(CounterKey::Str(s.to_string())),
462 Value::Label(l) => Some(CounterKey::Selector(Selector::Label(l.clone()))),
463 Value::Location(l) => Some(CounterKey::Selector(Selector::Location(*l))),
464 Value::Selector(s) => Some(CounterKey::Selector((**s).clone())),
465 _ => None,
466 }
467 }
468
469 pub fn same(&self, other: &CounterKey) -> bool {
470 match (self, other) {
471 (CounterKey::Page, CounterKey::Page) => true,
472 (CounterKey::Str(a), CounterKey::Str(b)) => a == b,
473 (CounterKey::Selector(a), CounterKey::Selector(b)) => selector_eq(a, b),
474 _ => false,
475 }
476 }
477
478 /// A key equal for equal counters in every pass, for the sequence memo.
479 fn memo_key(&self) -> Fingerprint {
480 let mut h = Fingerprinter::new();
481 match self {
482 CounterKey::Page => h.write_u8(0),
483 CounterKey::Str(s) => { h.write_u8(1); h.write_str(s); }
484 CounterKey::Selector(s) => { h.write_u8(2); fp::hash_selector(&mut h, s); }
485 }
486 h.finish()
487 }
488}
489
490#[derive(Clone, Debug)]
491pub struct Counter {
492 pub key: CounterKey,
493}
494
495impl Counter {
496 pub fn new(key: CounterKey) -> Self { Self { key } }
497
498 /// The counter an element steps: `counter(heading)` for a heading.
499 pub fn of(kind: ElemKind) -> Self { Self::new(CounterKey::Selector(Selector::Elem(kind, None))) }
500
501 pub fn page() -> Self { Self::new(CounterKey::Page) }
502
503 pub fn is_page(&self) -> bool { matches!(self.key, CounterKey::Page) }
504}
505
506/// How one element moves a counter. `Step(n)` steps level `n`.
507#[derive(Clone, Debug)]
508pub enum CounterUpdate {
509 Set(Vec<u64>),
510 Step(usize),
511 Func(Func),
512}
513
514impl CounterUpdate {
515 /// The update as a counter update element stores it in its `update` field.
516 pub fn to_value(&self) -> Value {
517 match self {
518 CounterUpdate::Set(ns) => Value::array(ns.iter().map(|n| Value::Int(*n as i64)).collect()),
519 CounterUpdate::Step(l) => {
520 let mut d = Dict::new();
521 d.insert("step", Value::Int(*l as i64));
522 Value::dict(d)
523 }
524 CounterUpdate::Func(f) => Value::Func(f.clone()),
525 }
526 }
527
528 pub fn from_value(v: &Value) -> Option<CounterUpdate> {
529 match v {
530 Value::Func(f) => Some(CounterUpdate::Func(f.clone())),
531 Value::Dict(d) => match d.get("step") {
532 Some(Value::Int(l)) if *l >= 1 => Some(CounterUpdate::Step(*l as usize)),
533 _ => None,
534 },
535 other => counter_state(other).ok().map(CounterUpdate::Set),
536 }
537 }
538}
539
540/// Typst's `CounterState::step`: missing levels down to `level` appear as 0, deeper ones are dropped,
541/// and level `level` goes up by `by`.
542pub fn step(state: &mut Vec<u64>, level: usize, by: u64) {
543 let level = level.max(1);
544 while state.len() < level {
545 state.push(0);
546 }
547 state.truncate(level);
548 if let Some(last) = state.last_mut() {
549 *last = last.saturating_add(by);
550 }
551}
552
553/// A counter state from a value: an integer, or an array of them, none negative.
554pub fn counter_state(v: &Value) -> Outcome<Vec<u64>> {
555 match v {
556 Value::Int(n) => {
557 if *n < 0 {
558 return Err(err!("number must be at least zero"; Input, Invalid));
559 }
560 Ok(vec![*n as u64])
561 }
562 Value::Array(a) => {
563 let mut out = Vec::with_capacity(a.len());
564 for x in a.iter() {
565 match x {
566 Value::Int(n) if *n >= 0 => out.push(*n as u64),
567 Value::Int(_) => return Err(err!("number must be at least zero"; Input, Invalid)),
568 other => return Err(err!(
569 "expected integer, found {}", other.ty().long_name(); Input, Invalid)),
570 }
571 }
572 Ok(out)
573 }
574 other => Err(err!("expected integer or array, found {}", other.ty().long_name(); Input, Invalid)),
575 }
576}
577
578pub fn state_value(ns: &[u64]) -> Value {
579 Value::array(ns.iter().map(|n| Value::Int(*n as i64)).collect())
580}
581
582/// Typst's `CounterState::first`: the top-level number, one for an empty state.
583fn first(ns: &[u64]) -> u64 { ns.first().copied().unwrap_or(1) }
584
585#[derive(Clone, Debug)]
586pub struct State {
587 pub key: String,
588 pub init: Value,
589}
590
591// Reads
592
593/// A question a pass asked the introspector. Counters and states are folds over queries, so these few
594/// primitives are all a pass can observe of layout.
595#[derive(Clone, Debug)]
596pub enum Question {
597 Query(Selector),
598 CountBefore(Selector, Location),
599 Page(Location),
600 Position(Location),
601 Pages,
602 PageNumbering(Location),
603}
604
605impl Question {
606 /// The answer, hashed, against an introspector.
607 pub fn answer(&self, intro: &Introspector) -> Outcome<Fingerprint> {
608 let mut h = Fingerprinter::new();
609 match self {
610 Question::Query(sel) => {
611 let found = res!(intro.query_indices(sel));
612 h.write_u64(found.len() as u64);
613 for i in found {
614 if let Some(r) = intro.records.get(i) {
615 hash_content(&mut h, &r.elem);
616 }
617 }
618 }
619 Question::CountBefore(sel, loc) => return Ok(count_answer(res!(intro.count_before(sel, *loc)))),
620 Question::Page(loc) => h.write_u64(intro.page(*loc).map(|p| p as u64 + 1).unwrap_or(0)),
621 Question::Position(loc) => match intro.position(*loc) {
622 Some(p) => {
623 h.write_u64(1);
624 h.write_u64(p.page as u64);
625 h.write_u64(p.x.0 as u64);
626 h.write_u64(p.y.0 as u64);
627 }
628 None => h.write_u64(0),
629 },
630 Question::Pages => h.write_u64(intro.pages as u64),
631 Question::PageNumbering(loc) => hash_value(&mut h, &intro.page_numbering(*loc)),
632 }
633 Ok(h.finish())
634 }
635
636 /// What was asked, as a key equal for equal questions in every pass.
637 pub fn key(&self) -> Fingerprint {
638 match self {
639 Question::Query(s) => Self::query_key(selector_fp(s)),
640 Question::CountBefore(s, l) => Self::count_key(selector_fp(s), *l),
641 Question::Page(l) => Self::loc_key(2, *l),
642 Question::Position(l) => Self::loc_key(3, *l),
643 Question::Pages => Self::bare_key(4),
644 Question::PageNumbering(l) => Self::loc_key(5, *l),
645 }
646 }
647
648 // The keys of the questions a fold asks again and again, from a selector hashed once.
649 fn query_key(sel: Fingerprint) -> Fingerprint {
650 let mut h = Fingerprinter::new();
651 h.write_u8(0);
652 h.write_fingerprint(sel);
653 h.finish()
654 }
655
656 fn count_key(sel: Fingerprint, loc: Location) -> Fingerprint {
657 let mut h = Fingerprinter::new();
658 h.write_u8(1);
659 h.write_fingerprint(sel);
660 h.write_u64(loc.0);
661 h.finish()
662 }
663
664 fn loc_key(tag: u8, loc: Location) -> Fingerprint {
665 let mut h = Fingerprinter::new();
666 h.write_u8(tag);
667 h.write_u64(loc.0);
668 h.finish()
669 }
670
671 fn bare_key(tag: u8) -> Fingerprint {
672 let mut h = Fingerprinter::new();
673 h.write_u8(tag);
674 h.finish()
675 }
676}
677
678/// The answer to a count-before question, from the count.
679fn count_answer(n: usize) -> Fingerprint {
680 let mut h = Fingerprinter::new();
681 h.write_u64(n as u64);
682 h.finish()
683}
684
685/// One introspection read: what was asked, a hash of the answer, and the counter or state it was
686/// asked for, which is what a non-convergence warning names.
687#[derive(Clone, Debug)]
688pub struct Read {
689 pub key: Fingerprint,
690 pub answer: Fingerprint,
691 pub question: Question,
692 pub subject: Option<Arc<str>>, // "value of `counter(heading)`"
693}
694
695impl PartialEq for Read {
696 fn eq(&self, other: &Self) -> bool { self.key == other.key && self.answer == other.answer }
697}
698
699impl Eq for Read {}
700
701impl std::hash::Hash for Read {
702 fn hash<H: std::hash::Hasher>(&self, state: &mut H) {
703 self.key.hash(state);
704 self.answer.hash(state);
705 }
706}
707
708/// A sequence folded over the matches of a selector, once per pass: a counter's states or a state's
709/// values, with where in document order each stop stands, so that a read finds its stop by a binary
710/// search and never by a rescan of the updates.
711#[derive(Debug)]
712struct Fold<T> {
713 sel: Selector, // what the sequence was folded over
714 fp: Fingerprint, // `sel` hashed, the selector part of every count question
715 all: Vec<u32>, // every match of `sel`, in document order
716 orders: Vec<u32>, // the matches that made a stop, in document order
717 stops: Vec<T>, // the initial stop, then one after each of `orders`
718 subject: Arc<str>, // the counter or state, as a warning names it
719}
720
721/// Every distinct read of the pass, and the counter and state sequences already folded against the
722/// introspector the pass reads, so that a document displaying its heading numbers folds the heading
723/// counter once, not once a heading.
724#[derive(Clone, Debug, Default)]
725pub struct ReadLog {
726 pub all: Vec<Read>,
727 seen: HashSet<Fingerprint>,
728 asks: u64, // every question put, new or repeated
729 subject: Option<Arc<str>>, // the counter or state being folded
730 memo_of: usize, // the introspector the memo was folded against
731 counters: HashMap<Fingerprint, Arc<Fold<(Vec<u64>, u32)>>>,
732 states: HashMap<Fingerprint, Arc<Fold<Value>>>,
733}
734
735impl ReadLog {
736 /// Records a question the pass has not asked yet. The question is built, and its answer hashed,
737 /// only when it is new, so a repeated question costs a key and a lookup.
738 fn note<F: FnOnce() -> Question>(&mut self, key: Fingerprint, intro: &Introspector, make: F) -> Outcome<()> {
739 self.asks += 1;
740 if self.seen.contains(&key) {
741 return Ok(());
742 }
743 let question = make();
744 let answer = res!(question.answer(intro));
745 self.push(key, question, answer);
746 Ok(())
747 }
748
749 /// How many questions the pass has put, a repeated one counted again, which `all` does not grow for. Equal
750 /// counts either side of a piece of work prove it asked nothing, so what it made may be kept without its
751 /// reads.
752 pub fn asks(&self) -> u64 {
753 self.asks
754 }
755
756 // Stores a new read whose answer the caller already knows.
757 fn push(&mut self, key: Fingerprint, question: Question, answer: Fingerprint) {
758 self.seen.insert(key);
759 self.all.push(Read { key, answer, question, subject: self.subject.clone() });
760 }
761
762 /// Does every read of the pass answer the same against `intro`? The fixpoint's convergence test.
763 pub fn holds(&self, intro: &Introspector) -> Outcome<bool> {
764 for r in &self.all {
765 if res!(r.question.answer(intro)) != r.answer {
766 return Ok(false);
767 }
768 }
769 Ok(true)
770 }
771
772 /// The reads that answer differently against `intro`, for the non-convergence warnings.
773 pub fn changed(&self, intro: &Introspector) -> Outcome<Vec<&Read>> {
774 let mut out = Vec::new();
775 for r in &self.all {
776 if res!(r.question.answer(intro)) != r.answer {
777 out.push(r);
778 }
779 }
780 Ok(out)
781 }
782
783 /// Drops the folded sequences when the engine now reads another introspector.
784 fn validate_memo(&mut self, intro: &Arc<Introspector>) {
785 let id = Arc::as_ptr(intro) as usize;
786 if self.memo_of != id {
787 self.counters.clear();
788 self.states.clear();
789 self.memo_of = id;
790 }
791 }
792}
793
794fn ask(engine: &mut Engine, q: Question) -> Outcome<()> {
795 let key = q.key();
796 engine.reads.note(key, &engine.intro, || q)
797}
798
799/// Runs `f` with the reads it makes attributed to `subject`.
800fn attributed<T, F: FnOnce(&mut Engine) -> Outcome<T>>(engine: &mut Engine, subject: Arc<str>, f: F) -> Outcome<T> {
801 let outer = engine.reads.subject.replace(subject);
802 let out = f(engine);
803 engine.reads.subject = outer;
804 out
805}
806
807fn counter_subject(counter: &Counter) -> Arc<str> {
808 match &counter.key {
809 CounterKey::Page => Arc::from("value of the page counter"),
810 key => Arc::from(fmt!("value of `counter({})`", lib::foundations::repr(&key.to_value()))),
811 }
812}
813
814fn state_subject(state: &State) -> Arc<str> {
815 Arc::from(fmt!("value of `state({})`", lib::foundations::repr(&Value::str(state.key.clone()))))
816}
817
818/// What a read that did not settle is reported as, in Typst's words: the counter or state it was made
819/// for, else the query or the location it asked about.
820pub fn describe(read: &Read, intro: &Introspector) -> String {
821 if let Some(s) = &read.subject {
822 return fmt!("{} did not converge", s);
823 }
824 let kind = |loc: &Location| intro.get(*loc).map(|c| c.func_kind().name()).unwrap_or("element");
825 match &read.question {
826 Question::Query(sel) | Question::CountBefore(sel, _) =>
827 fmt!("query for {} did not stabilize", format_selector(sel, "elements")),
828 Question::Page(l) => fmt!("page number of the {} did not stabilize", kind(l)),
829 Question::Position(l) => fmt!("{} position did not stabilize", kind(l)),
830 Question::PageNumbering(l) => fmt!("numbering of the page on which the {} is located did not stabilize",
831 kind(l)),
832 Question::Pages => "page count did not stabilize".to_string(),
833 }
834}
835
836/// A selector as Typst names what it matches in a warning.
837fn format_selector(sel: &Selector, what: &str) -> String {
838 match sel {
839 Selector::Elem(k, None) => fmt!("{} {}", k.name(), what),
840 Selector::Elem(k, _) => fmt!("matching {} {}", k.name(), what),
841 Selector::Label(l) => fmt!("{} labelled `<{}>`", what, l.as_str()),
842 other => fmt!("{} matching `{}`",
843 what, lib::foundations::repr(&Value::Selector(Arc::new(other.clone())))),
844 }
845}
846
847// Recorded introspection: what library code calls, so that every answer reaches the fixpoint.
848
849/// Every element the selector matches, in document order, from the previous pass.
850/// The document metadata a style chain carries: `set document(title:, author:, description:, keywords:)`,
851/// Typst's own defaults where unset. Content is read as its plain text, an array of strings joined with
852/// ", " for the one Info entry.
853pub fn document_info(styles: &StyleChain) -> Outcome<DocInfo> {
854 let plain = |v: Value| -> Option<String> {
855 match v {
856 Value::None => None,
857 Value::Content(c) => Some(c.plain_text()),
858 Value::Str(s) => Some(s.to_string()),
859 _ => None,
860 }
861 };
862 let joined = |v: Value| -> Option<String> {
863 match v {
864 Value::Array(a) => {
865 let parts: Vec<String> = a.iter().filter_map(|x| match x {
866 Value::Str(s) => Some(s.to_string()),
867 _ => None,
868 }).collect();
869 if parts.is_empty() { None } else { Some(parts.join(", ")) }
870 }
871 _ => None,
872 }
873 };
874 Ok(DocInfo {
875 title: plain(res!(model::common::style(styles, ElemKind::Document, "title"))),
876 author: joined(res!(model::common::style(styles, ElemKind::Document, "author"))),
877 subject: plain(res!(model::common::style(styles, ElemKind::Document, "description"))),
878 keywords: joined(res!(model::common::style(styles, ElemKind::Document, "keywords"))),
879 })
880}
881
882pub fn query(engine: &mut Engine, selector: &Selector) -> Outcome<Vec<Content>> {
883 engine.timed(Phase::Intro, |engine| {
884 let key = Question::query_key(selector_fp(selector));
885 res!(engine.reads.note(key, &engine.intro, || Question::Query(selector.clone())));
886 engine.intro.query(selector)
887 })
888}
889
890/// The one element carrying `label`, or Typst's error for none and for several. Answered without a
891/// context, as an element's own show asks it (`ref`, `link`).
892pub fn query_label(engine: &mut Engine, label: &Label, span: Span) -> Outcome<Content> {
893 match res!(query_label_opt(engine, label, span)) {
894 Some(c) => Ok(c),
895 None => Err(engine.error(DiagnosticKind::Type, span, fmt!("label `<{}>` does not exist in the document", label.as_str()))),
896 }
897}
898
899/// As [`query_label`], but a label absent from the document is `None`.
900pub fn query_label_opt(engine: &mut Engine, label: &Label, span: Span) -> Outcome<Option<Content>> {
901 let mut found = res!(query(engine, &Selector::Label(label.clone())));
902 match found.len() {
903 0 => Ok(None),
904 1 => Ok(found.pop()),
905 _ => Err(engine.error(DiagnosticKind::Type, span, fmt!("label `<{}>` occurs multiple times in the document", label.as_str()))),
906 }
907}
908
909pub fn position(engine: &mut Engine, loc: Location) -> Outcome<Option<Position>> {
910 engine.timed(Phase::Intro, |engine| {
911 res!(ask(engine, Question::Position(loc)));
912 Ok(engine.intro.position(loc))
913 })
914}
915
916/// The page `loc` landed on. Asked apart from its position, it settles as soon as the page does.
917pub fn page(engine: &mut Engine, loc: Location) -> Outcome<Option<u32>> {
918 engine.timed(Phase::Intro, |engine| {
919 res!(ask(engine, Question::Page(loc)));
920 Ok(engine.intro.page(loc))
921 })
922}
923
924pub fn pages(engine: &mut Engine) -> Outcome<u32> {
925 engine.timed(Phase::Intro, |engine| {
926 res!(ask(engine, Question::Pages));
927 Ok(engine.intro.pages)
928 })
929}
930
931pub fn page_numbering(engine: &mut Engine, loc: Location) -> Outcome<Value> {
932 engine.timed(Phase::Intro, |engine| {
933 res!(ask(engine, Question::PageNumbering(loc)));
934 Ok(engine.intro.page_numbering(loc))
935 })
936}
937
938/// The error Typst gives a context-only function called outside `context`.
939pub fn no_context(engine: &mut Engine, span: Span) -> Error<ErrTag> {
940 error_hints(engine, DiagnosticKind::Type, span, "can only be used when context is known", &[
941 "try wrapping this in a `context` expression",
942 "the `context` expression should wrap everything that depends on this function",
943 ])
944}
945
946/// `here()`: the location of the context in force, or the no-context error.
947pub fn here(engine: &mut Engine, span: Span) -> Outcome<Location> {
948 match engine.context.location {
949 Some(l) => Ok(l),
950 None => Err(no_context(engine, span)),
951 }
952}
953
954/// The styles of the context in force, or the no-context error.
955pub fn context_styles(engine: &mut Engine, span: Span) -> Outcome<StyleChain> {
956 match &engine.context.styles {
957 Some(s) => Ok(s.clone()),
958 None => Err(no_context(engine, span)),
959 }
960}
961
962/// Fails unless the selector can only match locatable elements, with Typst's message.
963pub fn check_locatable(engine: &mut Engine, span: Span, selector: &Selector) -> Outcome<()> {
964 match selector {
965 Selector::Elem(k, _) if !k.locatable() => Err(engine.error(DiagnosticKind::Type, span, fmt!("{} is not locatable", k.name()))),
966 Selector::Text(_) | Selector::Regex(_) => Err(engine.error(DiagnosticKind::Type, span, "text is not locatable")),
967 Selector::Or(ss) | Selector::And(ss) => {
968 for s in ss {
969 res!(check_locatable(engine, span, s));
970 }
971 Ok(())
972 }
973 Selector::Before { selector, end, .. } => {
974 res!(check_locatable(engine, span, selector));
975 check_locatable(engine, span, end)
976 }
977 Selector::After { selector, start, .. } => {
978 res!(check_locatable(engine, span, selector));
979 check_locatable(engine, span, start)
980 }
981 _ => Ok(()),
982 }
983}
984
985/// The one location a selector names, as `locate` and `counter.at` resolve it: a location stands for
986/// itself; anything else needs a context, then must match exactly one element.
987pub fn resolve_unique(engine: &mut Engine, span: Span, selector: &Selector) -> Outcome<Location> {
988 if let Selector::Location(l) = selector {
989 return Ok(*l);
990 }
991 if engine.context.location.is_none() {
992 return Err(no_context(engine, span));
993 }
994 unique(engine, span, selector)
995}
996
997/// As [`resolve_unique`] without the context check, for an element's own show: a label must occur
998/// exactly once; any other selector must match exactly one element.
999pub fn unique(engine: &mut Engine, span: Span, selector: &Selector) -> Outcome<Location> {
1000 if let Selector::Location(l) = selector {
1001 return Ok(*l);
1002 }
1003 let found = res!(query(engine, selector));
1004 match (selector, found.len()) {
1005 (_, 1) => match found[0].location() {
1006 Some(l) => Ok(l),
1007 None => Err(err!("A queried element has no location."; Bug)),
1008 },
1009 (Selector::Label(l), 0) => Err(engine.error(DiagnosticKind::Type, span, fmt!(
1010 "label `<{}>` does not exist in the document", l.as_str()))),
1011 (Selector::Label(l), _) => Err(engine.error(DiagnosticKind::Type, span, fmt!(
1012 "label `<{}>` occurs multiple times in the document", l.as_str()))),
1013 (_, 0) => Err(engine.error(DiagnosticKind::Type, span, "selector does not match any element")),
1014 _ => Err(engine.error(DiagnosticKind::Type, span, "selector matches multiple elements")),
1015 }
1016}
1017
1018/// The update an element makes to the counters that select it, Typst's `Count`: a counter update
1019/// applies itself, the model's counted elements step as `model::count_step` says (a numbered heading at
1020/// its level, a numbered figure or block equation and a footnote that is not a reference once), and any
1021/// other element a counter selects steps once.
1022pub fn element_update(elem: &Content) -> Option<CounterUpdate> {
1023 match elem.kind() {
1024 Some(ElemKind::CounterUpdate) => elem.field("update").and_then(CounterUpdate::from_value),
1025 Some(ElemKind::Heading) | Some(ElemKind::Figure) | Some(ElemKind::Equation) | Some(ElemKind::Footnote)
1026 => model::count_step(elem).map(CounterUpdate::Step),
1027 _ => Some(CounterUpdate::Step(1)),
1028 }
1029}
1030
1031/// The selector a counter's sequence is queried by: every counter update, or the key's own selector as
1032/// well. Updates of other counters are filtered out by key afterwards.
1033fn counter_selector(counter: &Counter) -> Selector {
1034 let updates = Selector::Elem(ElemKind::CounterUpdate, None);
1035 match &counter.key {
1036 CounterKey::Selector(s) => Selector::Or(vec![updates, s.clone()]),
1037 _ => updates,
1038 }
1039}
1040
1041/// Every state the counter passes through, with the page it was on, and the document order of each
1042/// element that moved it: the initial state, then one after each element. Folded once per pass.
1043fn counter_fold(engine: &mut Engine, counter: &Counter) -> Outcome<Arc<Fold<(Vec<u64>, u32)>>> {
1044 engine.reads.validate_memo(&engine.intro);
1045 let key = counter.key.memo_key();
1046 if let Some(fold) = engine.reads.counters.get(&key) {
1047 return Ok(fold.clone());
1048 }
1049 let subject = counter_subject(counter);
1050 let fold = Arc::new(res!(attributed(engine, subject.clone(), |engine| fold_counter(engine, counter, subject))));
1051 engine.reads.counters.insert(key, fold.clone());
1052 Ok(fold)
1053}
1054
1055fn fold_counter(engine: &mut Engine, counter: &Counter, subject: Arc<str>) -> Outcome<Fold<(Vec<u64>, u32)>> {
1056 let intro = engine.intro.clone();
1057 let sel = counter_selector(counter);
1058 let fp = selector_fp(&sel);
1059 res!(engine.reads.note(Question::query_key(fp), &intro, || Question::Query(sel.clone())));
1060 let all: Vec<u32> = res!(intro.query_indices(&sel)).into_iter().map(|i| i as u32).collect();
1061 let mut state = vec![if counter.is_page() { 1 } else { 0 }];
1062 let mut pg = 1u32;
1063 let mut orders = Vec::new();
1064 let mut stops = Vec::with_capacity(all.len() + 1);
1065 stops.push((state.clone(), pg));
1066 for i in &all {
1067 let e = match intro.records.get(*i as usize) {
1068 Some(r) => &r.elem,
1069 None => continue,
1070 };
1071 if !moves(counter, e) {
1072 continue;
1073 }
1074 if counter.is_page() {
1075 if let Some(loc) = e.location() {
1076 let at = res!(page(engine, loc)).unwrap_or(1);
1077 if at > pg {
1078 step(&mut state, 1, (at - pg) as u64);
1079 }
1080 pg = at;
1081 }
1082 }
1083 if let Some(update) = element_update(e) {
1084 state = res!(apply_update(engine, e.span(), &state, update));
1085 }
1086 orders.push(*i);
1087 stops.push((state.clone(), pg));
1088 }
1089 Ok(Fold { sel, fp, all, orders, stops, subject })
1090}
1091
1092fn apply_update(engine: &mut Engine, span: Span, state: &[u64], update: CounterUpdate) -> Outcome<Vec<u64>> {
1093 match update {
1094 CounterUpdate::Set(ns) => Ok(ns),
1095 CounterUpdate::Step(l) => {
1096 let mut s = state.to_vec();
1097 step(&mut s, l, 1);
1098 Ok(s)
1099 }
1100 CounterUpdate::Func(f) => {
1101 // A closure's own span, where Typst reports an argument it cannot take.
1102 let span = match &f {
1103 Func::Closure(c) if !c.span().is_detached() => c.span(),
1104 _ => span,
1105 };
1106 let mut args = Args::new(span);
1107 for n in state {
1108 args.push(span, Value::Int(*n as i64));
1109 }
1110 // An update function runs without a context, as Typst calls it.
1111 let saved = std::mem::take(&mut engine.context);
1112 let v = engine.call_func(&f, args);
1113 engine.context = saved;
1114 match counter_state(&res!(v)) {
1115 Ok(s) => Ok(s),
1116 Err(e) => Err(engine.error(DiagnosticKind::Type, span, e.plain())),
1117 }
1118 }
1119 }
1120}
1121
1122/// The stop of a fold that sits at `loc`: after every match at or before it, or after all of them when
1123/// the pages did not place `loc`. Only the updates of this counter or state made stops, so a binary
1124/// search of their document order finds it.
1125fn stop_at<T: Clone>(engine: &mut Engine, fold: &Fold<T>, loc: Location) -> Outcome<T> {
1126 let at = engine.intro.order(loc);
1127 let key = Question::count_key(fold.fp, loc);
1128 engine.reads.asks += 1;
1129 if !engine.reads.seen.contains(&key) {
1130 // The count of every match at or before `loc`, as `Introspector::count_before` answers it.
1131 let n = match at {
1132 Some(a) => fold.all.partition_point(|i| *i as usize <= a),
1133 None => fold.all.len(),
1134 };
1135 engine.reads.push(key, Question::CountBefore(fold.sel.clone(), loc), count_answer(n));
1136 }
1137 let n = match at {
1138 Some(a) => fold.orders.partition_point(|i| *i as usize <= a),
1139 None => fold.orders.len(),
1140 };
1141 match fold.stops.get(n).or_else(|| fold.stops.last()) {
1142 Some(s) => Ok(s.clone()),
1143 None => Err(err!("A sequence has no initial stop."; Bug)),
1144 }
1145}
1146
1147/// Does `e` move `counter`? Its own updates do, and the elements its selector matches.
1148fn moves(counter: &Counter, e: &Content) -> bool {
1149 if e.is(ElemKind::CounterUpdate) {
1150 return e.field("key").and_then(CounterKey::from_value).map(|k| k.same(&counter.key)).unwrap_or(false);
1151 }
1152 true
1153}
1154
1155/// The counter's value at a location: after every update at or before it.
1156pub fn counter_at(engine: &mut Engine, counter: &Counter, loc: Location) -> Outcome<Vec<u64>> {
1157 engine.timed(Phase::Intro, |engine| {
1158 let fold = res!(counter_fold(engine, counter));
1159 attributed(engine, fold.subject.clone(), |engine| {
1160 let (mut state, pg) = res!(stop_at(engine, &fold, loc));
1161 if counter.is_page() {
1162 let at = res!(page(engine, loc)).unwrap_or(1);
1163 if at > pg {
1164 step(&mut state, 1, (at - pg) as u64);
1165 }
1166 }
1167 Ok(state)
1168 })
1169 })
1170}
1171
1172/// The counter's value at the end of the document.
1173pub fn counter_final(engine: &mut Engine, counter: &Counter) -> Outcome<Vec<u64>> {
1174 engine.timed(Phase::Intro, |engine| {
1175 let fold = res!(counter_fold(engine, counter));
1176 attributed(engine, fold.subject.clone(), |engine| {
1177 let (mut state, pg) = match fold.stops.last() {
1178 Some(s) => s.clone(),
1179 None => return Err(err!("A counter sequence has no initial state."; Bug)),
1180 };
1181 if counter.is_page() {
1182 let total = res!(pages(engine)).max(1);
1183 if total > pg {
1184 step(&mut state, 1, (total - pg) as u64);
1185 }
1186 }
1187 Ok(state)
1188 })
1189 })
1190}
1191
1192/// The top-level number at `loc` and at the end, together: what `display(both: true)` formats.
1193pub fn counter_both(engine: &mut Engine, counter: &Counter, loc: Location) -> Outcome<Vec<u64>> {
1194 let at = res!(counter_at(engine, counter, loc));
1195 let fin = res!(counter_final(engine, counter));
1196 Ok(vec![first(&at), first(&fin)])
1197}
1198
1199/// The numbering a counter displays with when none is given, Typst's `matching_numbering`: the page's
1200/// for the page counter; for a counted element's counter, that of the element at `loc` when it is one,
1201/// else the style chain's.
1202fn matching_numbering(
1203 engine: &mut Engine,
1204 counter: &Counter,
1205 loc: Location,
1206 styles: Option<&StyleChain>,
1207)
1208 -> Outcome<Option<Value>>
1209{
1210 let kind = match &counter.key {
1211 CounterKey::Page => return page_numbering(engine, loc).map(|v| match v {
1212 Value::None => None,
1213 v => Some(v),
1214 }),
1215 CounterKey::Selector(Selector::Elem(k, _)) => *k,
1216 _ => return Ok(None),
1217 };
1218 if !matches!(kind, ElemKind::Heading | ElemKind::Figure | ElemKind::Equation | ElemKind::Footnote) {
1219 return Ok(None);
1220 }
1221 let here_elem = res!(query(engine, &Selector::Location(loc)));
1222 if let Some(e) = here_elem.first().filter(|e| e.is(kind)) {
1223 match e.field("numbering") {
1224 None | Some(Value::None) | Some(Value::Auto) => (),
1225 Some(n) => return Ok(Some(n.clone())),
1226 }
1227 }
1228 let chain = match styles {
1229 Some(c) => c,
1230 None => return Ok(None),
1231 };
1232 match kind.field_id("numbering") {
1233 Some(id) => Ok(match res!(chain.get(kind, id)) {
1234 None | Some(Value::None) | Some(Value::Auto) => None,
1235 Some(n) => Some(n),
1236 }),
1237 None => Ok(None),
1238 }
1239}
1240
1241/// `counter.display()`: the counter at `loc` (both numbers with `both`) formatted with `numbering`, or
1242/// with the numbering the counted element or the page has, falling back to `"1.1"`. The numbering runs
1243/// in a context at `loc`. A `trimmed` pattern drops its first prefix and its suffix, as a reference to
1244/// the element shows its number.
1245pub fn counter_display(
1246 engine: &mut Engine,
1247 counter: &Counter,
1248 numbering: Option<Value>,
1249 both: bool,
1250 trimmed: bool,
1251 loc: Location,
1252 styles: Option<&StyleChain>,
1253)
1254 -> Outcome<Value>
1255{
1256 let state = if both {
1257 res!(counter_both(engine, counter, loc))
1258 } else {
1259 res!(counter_at(engine, counter, loc))
1260 };
1261 let numbering = match numbering {
1262 Some(n) => n,
1263 None => res!(matching_numbering(engine, counter, loc, styles)).unwrap_or_else(|| Value::str("1.1")),
1264 };
1265 let saved = std::mem::replace(&mut engine.context, Context {
1266 location: Some(loc),
1267 styles: styles.cloned(),
1268 });
1269 let out = if trimmed {
1270 lib::numbering::apply_trimmed(engine, &numbering, &state)
1271 } else {
1272 lib::numbering::apply(engine, &numbering, &state)
1273 };
1274 engine.context = saved;
1275 out
1276}
1277
1278/// Typst's `Counter::display_at`: an element's counter at its location with a numbering, as a heading,
1279/// figure, equation or footnote shows its own number and a reference shows its target's. Recorded, so
1280/// the fixpoint runs again when a number moves.
1281pub fn display_at(
1282 engine: &mut Engine,
1283 counter: &Counter,
1284 loc: Location,
1285 numbering: &Value,
1286 trimmed: bool,
1287 styles: Option<&StyleChain>,
1288)
1289 -> Outcome<Value>
1290{
1291 counter_display(engine, counter, Some(numbering.clone()), false, trimmed, loc, styles)
1292}
1293
1294// States
1295
1296fn state_selector() -> Selector { Selector::Elem(ElemKind::StateUpdate, None) }
1297
1298fn updates(state: &State, e: &Content) -> bool {
1299 matches!(e.field("key"), Some(Value::Str(k)) if **k == state.key)
1300}
1301
1302/// Every value the state passes through: the initial one, then one after each of its updates. Folded
1303/// once per pass.
1304fn state_fold(engine: &mut Engine, state: &State) -> Outcome<Arc<Fold<Value>>> {
1305 engine.reads.validate_memo(&engine.intro);
1306 let mut h = Fingerprinter::new();
1307 h.write_str(&state.key);
1308 hash_value(&mut h, &state.init);
1309 let key = h.finish();
1310 if let Some(fold) = engine.reads.states.get(&key) {
1311 return Ok(fold.clone());
1312 }
1313 let subject = state_subject(state);
1314 let fold = Arc::new(res!(attributed(engine, subject.clone(), |engine| fold_state(engine, state, subject))));
1315 engine.reads.states.insert(key, fold.clone());
1316 Ok(fold)
1317}
1318
1319fn fold_state(engine: &mut Engine, state: &State, subject: Arc<str>) -> Outcome<Fold<Value>> {
1320 let intro = engine.intro.clone();
1321 let sel = state_selector();
1322 let fp = selector_fp(&sel);
1323 res!(engine.reads.note(Question::query_key(fp), &intro, || Question::Query(sel.clone())));
1324 let all: Vec<u32> = res!(intro.query_indices(&sel)).into_iter().map(|i| i as u32).collect();
1325 let mut v = state.init.clone();
1326 let mut orders = Vec::new();
1327 let mut stops = Vec::with_capacity(all.len() + 1);
1328 stops.push(v.clone());
1329 for i in &all {
1330 let e = match intro.records.get(*i as usize) {
1331 Some(r) => &r.elem,
1332 None => continue,
1333 };
1334 if !updates(state, e) {
1335 continue;
1336 }
1337 v = match e.field("update") {
1338 Some(Value::Func(f)) => {
1339 let f = f.clone();
1340 let mut args = Args::new(e.span());
1341 args.push(e.span(), v);
1342 // An update function runs without a context, as Typst calls it.
1343 let saved = std::mem::take(&mut engine.context);
1344 let out = engine.call_func(&f, args);
1345 engine.context = saved;
1346 res!(out)
1347 }
1348 Some(x) => x.clone(),
1349 None => v,
1350 };
1351 orders.push(*i);
1352 stops.push(v.clone());
1353 }
1354 Ok(Fold { sel, fp, all, orders, stops, subject })
1355}
1356
1357pub fn state_at(engine: &mut Engine, state: &State, loc: Location) -> Outcome<Value> {
1358 engine.timed(Phase::Intro, |engine| {
1359 let fold = res!(state_fold(engine, state));
1360 attributed(engine, fold.subject.clone(), |engine| stop_at(engine, &fold, loc))
1361 })
1362}
1363
1364pub fn state_final(engine: &mut Engine, state: &State) -> Outcome<Value> {
1365 engine.timed(Phase::Intro, |engine| {
1366 let fold = res!(state_fold(engine, state));
1367 Ok(fold.stops.last().cloned().unwrap_or(Value::None))
1368 })
1369}
1370
1371// Equality and hashing that are stable from pass to pass
1372
1373/// Structural selector equality, for matching a counter update's key with its counter.
1374pub fn selector_eq(a: &Selector, b: &Selector) -> bool {
1375 match (a, b) {
1376 (Selector::Elem(ka, fa), Selector::Elem(kb, fb)) => ka == kb && match (fa, fb) {
1377 (None, None) => true,
1378 (Some(x), Some(y)) => x.len() == y.len() && x.iter().all(|(id, v)|
1379 y.iter().any(|(id2, w)| id == id2 && ops::equal(v, w))),
1380 _ => false,
1381 },
1382 (Selector::Label(x), Selector::Label(y)) => x == y,
1383 (Selector::Text(x), Selector::Text(y)) => x == y,
1384 (Selector::Regex(x), Selector::Regex(y)) => x.pattern == y.pattern,
1385 (Selector::Location(x), Selector::Location(y)) => x == y,
1386 (Selector::Or(x), Selector::Or(y)) | (Selector::And(x), Selector::And(y)) =>
1387 x.len() == y.len() && x.iter().zip(y.iter()).all(|(p, q)| selector_eq(p, q)),
1388 (Selector::Before { selector: s1, end: e1, inclusive: i1 },
1389 Selector::Before { selector: s2, end: e2, inclusive: i2 }) =>
1390 i1 == i2 && selector_eq(s1, s2) && selector_eq(e1, e2),
1391 (Selector::After { selector: s1, start: e1, inclusive: i1 },
1392 Selector::After { selector: s2, start: e2, inclusive: i2 }) =>
1393 i1 == i2 && selector_eq(s1, s2) && selector_eq(e1, e2),
1394 _ => false,
1395 }
1396}
1397
1398/// A selector hashed by its structure, equal for equal selectors in every pass.
1399fn selector_fp(s: &Selector) -> Fingerprint {
1400 let mut h = Fingerprinter::new();
1401 fp::hash_selector(&mut h, s);
1402 h.finish()
1403}
1404
1405/// Hashes content by what a reader of a query result can observe: its structure, which [`fp`] hashes
1406/// span-free, and the locations in it, which a query reader sees and a structural fingerprint does not.
1407pub fn hash_content(h: &mut Fingerprinter, c: &Content) {
1408 h.write_fingerprint(c.fingerprint());
1409 hash_locations(h, c);
1410}
1411
1412// The locations of the content, in walk order. The structure is already in the hash, so the walk is
1413// unambiguous.
1414fn hash_locations(h: &mut Fingerprinter, c: &Content) {
1415 match c {
1416 Content::Elem(e) => {
1417 hash_location(h, e.location);
1418 let mut fields: Vec<&(FieldId, Value)> = e.fields.iter().collect();
1419 fields.sort_by_key(|(id, _)| id.0);
1420 for (_, v) in fields {
1421 hash_value_locations(h, v);
1422 }
1423 }
1424 Content::Sequence(s) => {
1425 hash_location(h, s.location);
1426 for k in &s.children {
1427 hash_locations(h, k);
1428 }
1429 }
1430 Content::Styled(s) => hash_locations(h, &s.child),
1431 }
1432}
1433
1434fn hash_location(h: &mut Fingerprinter, l: Option<Location>) {
1435 match l {
1436 Some(l) => { h.write_u8(1); h.write_u64(l.0); }
1437 None => h.write_u8(0),
1438 }
1439}
1440
1441fn hash_value_locations(h: &mut Fingerprinter, v: &Value) {
1442 match v {
1443 Value::Content(c) => hash_locations(h, c),
1444 Value::Array(a) => for x in a.iter() { hash_value_locations(h, x); },
1445 Value::Dict(d) => for (_, x) in d.iter() { hash_value_locations(h, x); },
1446 Value::Args(a) => for arg in a.items.iter() { hash_value_locations(h, &arg.value); },
1447 _ => (),
1448 }
1449}
1450
1451/// Hashes a value by its structure, span-free ([`fp::hash_value`]), then the locations of any content
1452/// in it, which a reader of the value sees.
1453pub fn hash_value(h: &mut Fingerprinter, v: &Value) {
1454 fp::hash_value(h, v);
1455 hash_value_locations(h, v);
1456}
1457
1458/// `location.position()`: the page and the top-left point, as a dictionary.
1459pub fn position_dict(p: Position) -> Value {
1460 let mut d = Dict::new();
1461 d.insert("page", Value::Int(p.page as i64));
1462 d.insert("x", Value::Length(Length::pt(p.x.to_pt())));
1463 d.insert("y", Value::Length(Length::pt(p.y.to_pt())));
1464 Value::dict(d)
1465}
1466
1467/// The space `measure` offers when a dimension is `auto`: as large as a length can be.
1468pub const UNBOUNDED: Sp = Sp(i32::MAX);
1469
1470/// Runs `f` as `measure` runs its layout: under a fresh root locator, as Typst's `measure` lays out under
1471/// `Locator::root()`, so what it realises takes none of the document's ordinals, and the locator in force
1472/// is put back whatever `f` returns. Nothing a measured layout places is recorded: the builder is reached
1473/// only by `driver::place_page`, and a measured layout never places a page, so there is none to detach.
1474pub fn detached<T, F: FnOnce(&mut Engine) -> Outcome<T>>(engine: &mut Engine, f: F) -> Outcome<T> {
1475 let outer = std::mem::take(&mut engine.locator);
1476 let out = f(engine);
1477 engine.locator = outer;
1478 out
1479}