Oregami
Repositories/oxedyne/fe2o3

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

5.0 KiB, 53 runs

created by r1870400018:63498, 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// A location is a hash of (where the realisation stands, element kind, the fingerprint of the element's
2// content, ordinal among the equal ones there). No source position enters it, so the same element keeps its
3// location from pass to pass and across an edit elsewhere in the source; an edit changes the location of the
4// edited element and of the elements that hold it, and of nothing else.
5//
6// Where the realisation stands is a [`Place`], Typst's `Locator`: a position in the tree of layouts, hashed
7// from the places above it. An element that lays a body of its own out is given its place when it is
8// realised, as Typst gives a child its sublocator, and every layout of its body, a measurement or a second
9// attempt in a region a footnote has shortened, starts afresh at that place. The same body then realises to
10// the same locations however often it is laid out, as Typst's `Locator::relayout` has it, and a footnote
11// within a block is placed once, not once for each layout of the block.
12//
13// A place is keyed by the element's shell (its kind and the fields that hold no content) and its ordinal
14// among the elements of that shell at the place above, never by what the element holds. Typing into a
15// paragraph then moves the paragraph's own location and those of the elements that hold it, and leaves the
16// place of the paragraph, so every located element inside it keeps its location and an introspector from
17// the pass before still answers the questions those elements ask. Inserting or deleting a container of
18// the same shell renumbers the places of the containers after it, a known limit that an alias from the
19// renumbered place to the one the introspector recorded would remove.
20
21use crate::eval::content::ElemKind;
22use crate::ledger::{
23 AnchorId,
24 AnchorKind,
25};
26
27use oxedyne_fe2o3_core::prelude::*;
28use oxedyne_fe2o3_hash::fingerprint::Fingerprint;
29use oxedyne_fe2o3_hash::fingerprint::Fingerprinter;
30
31use std::collections::HashMap;
32
33#[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)]
34pub struct Location(pub u64);
35
36impl Location {
37 /// The ledger anchor that records where this location landed.
38 pub fn anchor(self) -> AnchorId { AnchorId::new(AnchorKind::Location, fmt!("{:016x}", self.0)) }
39}
40
41/// A position in the tree of layouts: what a body is realised under. The root, where the document's own
42/// level is realised, is the default.
43#[derive(Clone, Copy, Debug, Default, PartialEq, Eq, Hash)]
44pub struct Place(pub u64);
45
46impl Place {
47 /// The place for content laid out on behalf of a located element, as Typst's `Locator::synthesize`: a
48 /// footnote's entry, read after the note.
49 pub fn synthesise(loc: Location) -> Self { Place(fnv(&[DOMAIN_SYNTH, loc.0])) }
50}
51
52// What a hash is for, so a location, a place and a synthesised place of one key never meet.
53const DOMAIN_LOCATION: u64 = 1;
54const DOMAIN_PLACE: u64 = 2;
55const DOMAIN_SYNTH: u64 = 3;
56
57/// Hands out locations and places during one realisation, at one place; `reset` before each pass. The
58/// ordinals count the elements of one kind and one fingerprint (the content's for a location, the shell's for
59/// a place) within the place, so another realisation at the same place, begun afresh with [`Locator::new`],
60/// hands out the same ones.
61#[derive(Clone, Debug, Default)]
62pub struct Locator {
63 place: Place,
64 seen: HashMap<u128, u32>,
65}
66
67impl Locator {
68 /// A locator for a realisation at `place`, counting from nothing.
69 pub fn new(place: Place) -> Self { Self { place, seen: HashMap::new() } }
70
71 pub fn reset(&mut self) { *self = Self::default(); }
72
73 pub fn place(&self) -> Place { self.place }
74
75 /// The place and the ordinals handed out so far, sorted, for the flow's carry fingerprint: how many
76 /// were handed out and how often, never which.
77 pub fn carry(&self) -> (Place, Vec<u32>) {
78 let mut counts: Vec<u32> = self.seen.values().copied().collect();
79 counts.sort_unstable();
80 (self.place, counts)
81 }
82
83 /// The location of an element of `kind` whose content has the fingerprint `fp`, met in this realisation.
84 pub fn locate(&mut self, kind: ElemKind, fp: Fingerprint) -> Location {
85 Location(self.next_hash(DOMAIN_LOCATION, kind, fp))
86 }
87
88 /// The place of an element met in this realisation, for a body it lays out later: Typst's sublocator. The
89 /// element is told by its `shell`, which leaves out what it holds, and by its ordinal among the same
90 /// shell here.
91 pub fn next(&mut self, kind: ElemKind, shell: Fingerprint) -> Place {
92 Place(self.next_hash(DOMAIN_PLACE, kind, shell))
93 }
94
95 fn next_hash(&mut self, domain: u64, kind: ElemKind, fp: Fingerprint) -> u64 {
96 let mut h = Fingerprinter::new();
97 h.write_u64(domain);
98 h.write_u64(self.place.0);
99 h.write_u64(kind as u64);
100 h.write_fingerprint(fp);
101 let base = h.finish();
102 let n = self.seen.entry(base.as_u128()).or_insert(0);
103 let mut h = Fingerprinter::new();
104 h.write_fingerprint(base);
105 h.write_u64(*n as u64);
106 *n += 1;
107 h.finish().fold()
108 }
109}
110
111// Folds the words to the 64 bits a location and a place hold.
112fn fnv(words: &[u64]) -> u64 {
113 let mut h = Fingerprinter::new();
114 for w in words {
115 h.write_u64(*w);
116 }
117 h.finish().fold()
118}