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 | |
| 21 | use crate::eval::content::ElemKind; |
| 22 | use crate::ledger::{ |
| 23 | AnchorId, |
| 24 | AnchorKind, |
| 25 | }; |
| 26 | |
| 27 | use oxedyne_fe2o3_core::prelude::*; |
| 28 | use oxedyne_fe2o3_hash::fingerprint::Fingerprint; |
| 29 | use oxedyne_fe2o3_hash::fingerprint::Fingerprinter; |
| 30 | |
| 31 | use std::collections::HashMap; |
| 32 | |
| 33 | #[derive(Clone, Copy, Debug, PartialEq, Eq, PartialOrd, Ord, Hash)] |
| 34 | pub struct Location(pub u64); |
| 35 | |
| 36 | impl 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)] |
| 44 | pub struct Place(pub u64); |
| 45 | |
| 46 | impl 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. |
| 53 | const DOMAIN_LOCATION: u64 = 1; |
| 54 | const DOMAIN_PLACE: u64 = 2; |
| 55 | const 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)] |
| 62 | pub struct Locator { |
| 63 | place: Place, |
| 64 | seen: HashMap<u128, u32>, |
| 65 | } |
| 66 | |
| 67 | impl 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. |
| 112 | fn 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 | } |