Oregami
Repositories/oxedyne/fe2o3

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

17.7 KiB, 23 runs

created by r1870400018:68577, 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//! Span-free structural fingerprints of values, styles and selectors.
2//!
3//! A fingerprint stands for what a value is, never for where it was written: no span, no byte offset
4//! and no source position enters one, so the same text at a shifted offset hashes alike. A closure is
5//! the exception that proves the rule: it hashes by its parameters, its body's syntax text, its
6//! captured values and the file it was written in, because a relative path in its body resolves
7//! against that file. There is no debug-form fallback for a value that can hold content; every
8//! [`Value`] variant is matched, so a variant added later fails to compile until it is hashed.
9//!
10//! Content is hashed here one node at a time ([`elem_fp`], [`seq_fp`], [`styled_fp`]), each writing
11//! its children's fingerprints, which [`Content::fingerprint`] reads from a cell beside the content,
12//! so a shared subtree is hashed once. A content fingerprint leaves out the span, the location and
13//! the place; a reader that sees locations adds them (`intro::hash_content`).
14//!
15//! The cells are kept honest by type. [`Shared`] is the only handle content, an element or a style
16//! list is held by, and it hands out `&mut` only through [`Shared::edit`] and [`Shared::take`], which
17//! forget the fingerprint. `Arc::make_mut` on a unique `Arc` does not clone, so a clone's empty cell
18//! alone would not do: an edit that skipped the reset would leave the old fingerprint on changed
19//! content, and the compiler now refuses any path that could.
20
21use crate::eval::args::Args;
22use crate::eval::content::{
23 Elem,
24 FieldId,
25 Sequence,
26 Styled,
27};
28use crate::eval::func::{
29 Closure,
30 Func,
31 Param,
32};
33use crate::eval::intro::{
34 CounterKey,
35};
36use crate::eval::scope::Scope;
37use crate::eval::select::Selector;
38use crate::eval::styles::{
39 Property,
40 Recipe,
41 RecipeIndex,
42 Style,
43 Styles,
44 Transformation,
45};
46use crate::eval::value::{
47 Alignment,
48 Angle,
49 Color,
50 Dash,
51 DashItem,
52 Datetime,
53 Direction,
54 Gradient,
55 GradientKind,
56 Label,
57 Length,
58 Paint,
59 Ratio,
60 Stroke,
61 SymVariants,
62 Symbol,
63 Tiling,
64 Value,
65};
66
67use oxedyne_fe2o3_core::prelude::*;
68use oxedyne_fe2o3_hash::fingerprint::Fingerprint;
69use oxedyne_fe2o3_hash::fingerprint::Fingerprinter;
70use oxedyne_fe2o3_hash::fingerprint::LazyFingerprint;
71
72use std::fmt;
73use std::ops::Deref;
74use std::sync::Arc;
75
76// Hashes a presence flag, then the value if there is one.
77fn hash_opt<T, F: FnOnce(&mut Fingerprinter, &T)>(h: &mut Fingerprinter, v: &Option<T>, f: F) {
78 match v {
79 Some(x) => { h.write_u8(1); f(h, x); }
80 None => h.write_u8(0),
81 }
82}
83
84fn hash_length(h: &mut Fingerprinter, l: &Length) {
85 h.write_f64(l.abs);
86 h.write_f64(l.em);
87}
88
89fn hash_ratios(h: &mut Fingerprinter, r: &(Ratio, Ratio)) {
90 h.write_f64(r.0.0);
91 h.write_f64(r.1.0);
92}
93
94fn hash_color(h: &mut Fingerprinter, c: &Color) {
95 h.write_u8(c.space as u8);
96 for x in c.c {
97 h.write_f32(x);
98 }
99 h.write_f32(c.alpha);
100}
101
102fn hash_angle(h: &mut Fingerprinter, a: &Angle) { h.write_f64(a.0); }
103
104fn hash_gradient(h: &mut Fingerprinter, g: &Gradient) {
105 match &g.kind {
106 GradientKind::Linear { angle } => {
107 h.write_u8(0);
108 hash_angle(h, angle);
109 }
110 GradientKind::Radial { center, radius, focal_center, focal_radius } => {
111 h.write_u8(1);
112 hash_ratios(h, center);
113 h.write_f64(radius.0);
114 hash_ratios(h, focal_center);
115 h.write_f64(focal_radius.0);
116 }
117 GradientKind::Conic { center, angle } => {
118 h.write_u8(2);
119 hash_ratios(h, center);
120 hash_angle(h, angle);
121 }
122 }
123 h.write_usize(g.stops.len());
124 for (c, r) in &g.stops {
125 hash_color(h, c);
126 h.write_f64(r.0);
127 }
128 h.write_u8(g.space as u8);
129 h.write_u8(g.relative as u8);
130}
131
132fn hash_tiling(h: &mut Fingerprinter, t: &Tiling) {
133 h.write_fingerprint(t.body.fingerprint());
134 hash_opt(h, &t.size, |h, s| {
135 hash_length(h, &s.0);
136 hash_length(h, &s.1);
137 });
138 hash_length(h, &t.spacing.0);
139 hash_length(h, &t.spacing.1);
140 h.write_u8(t.relative as u8);
141}
142
143fn hash_paint(h: &mut Fingerprinter, p: &Paint) {
144 match p {
145 Paint::Color(c) => { h.write_u8(0); hash_color(h, c); }
146 Paint::Gradient(g) => { h.write_u8(1); hash_gradient(h, g); }
147 Paint::Tiling(t) => { h.write_u8(2); hash_tiling(h, t); }
148 }
149}
150
151fn hash_dash(h: &mut Fingerprinter, d: &Dash) {
152 h.write_usize(d.array.len());
153 for item in &d.array {
154 match item {
155 DashItem::Len(l) => { h.write_u8(0); hash_length(h, l); }
156 DashItem::Dot => h.write_u8(1),
157 }
158 }
159 hash_length(h, &d.phase);
160}
161
162fn hash_stroke(h: &mut Fingerprinter, s: &Stroke) {
163 hash_opt(h, &s.paint, hash_paint);
164 hash_opt(h, &s.thickness, hash_length);
165 hash_opt(h, &s.cap, |h, c| h.write_u8(*c as u8));
166 hash_opt(h, &s.join, |h, j| h.write_u8(*j as u8));
167 hash_opt(h, &s.dash, |h, d| hash_opt(h, d, hash_dash));
168 hash_opt(h, &s.miter_limit, |h, m| h.write_f64(*m));
169}
170
171fn hash_alignment(h: &mut Fingerprinter, a: &Alignment) {
172 hash_opt(h, &a.x, |h, x| h.write_u8(*x as u8));
173 hash_opt(h, &a.y, |h, y| h.write_u8(*y as u8));
174}
175
176fn hash_symbol(h: &mut Fingerprinter, s: &Symbol) {
177 match &s.variants {
178 SymVariants::Single(t) => {
179 h.write_u8(0);
180 h.write_str(t);
181 }
182 SymVariants::Static(rows) => {
183 h.write_u8(1);
184 h.write_usize(rows.len());
185 for (m, t) in rows.iter() {
186 h.write_str(m);
187 h.write_str(t);
188 }
189 }
190 SymVariants::Runtime(rows) => {
191 h.write_u8(2);
192 h.write_usize(rows.len());
193 for (m, t) in rows.iter() {
194 h.write_str(m);
195 h.write_str(t);
196 }
197 }
198 }
199 h.write_str(&s.modifiers);
200}
201
202fn hash_datetime(h: &mut Fingerprinter, d: &Datetime) {
203 hash_opt(h, &d.year, |h, v| h.write_i32(*v));
204 hash_opt(h, &d.month, |h, v| h.write_u8(*v));
205 hash_opt(h, &d.day, |h, v| h.write_u8(*v));
206 hash_opt(h, &d.hour, |h, v| h.write_u8(*v));
207 hash_opt(h, &d.minute, |h, v| h.write_u8(*v));
208 hash_opt(h, &d.second, |h, v| h.write_u8(*v));
209}
210
211fn hash_direction(h: &mut Fingerprinter, d: &Direction) { h.write_u8(*d as u8); }
212
213/// Hashes a scope's own frame by name, and any intermediate frame above it; the parentless root is the
214/// standard library, which every evaluation shares, and is left out.
215fn hash_scope(h: &mut Fingerprinter, s: &Scope) {
216 let mut frame = Some(s);
217 let mut first = true;
218 while let Some(f) = frame {
219 if !first && f.parent.is_none() {
220 break;
221 }
222 first = false;
223 let mut names: Vec<&String> = f.map.keys().collect();
224 names.sort();
225 h.write_usize(names.len());
226 for n in names {
227 h.write_str(n);
228 if let Some(b) = f.map.get(n) {
229 hash_value(h, &b.value);
230 }
231 }
232 frame = f.parent.as_deref();
233 }
234}
235
236/// The fingerprint of a closure: its name, parameters, body text, file and everything it captured.
237pub fn closure_fp(c: &Closure) -> Fingerprint {
238 let mut h = Fingerprinter::new();
239 hash_opt(&mut h, &c.name(), |h, n| h.write_str(n));
240 h.write_usize(c.params().len());
241 for p in c.params() {
242 match p {
243 Param::Pos(node) => { h.write_u8(0); h.write_str(&node.full_text()); }
244 Param::Named { name, default } => { h.write_u8(1); h.write_str(name); hash_value(&mut h, default); }
245 Param::Sink(name) => { h.write_u8(2); hash_opt(&mut h, name, |h, n| h.write_str(n)); }
246 }
247 }
248 h.write_str(&c.body().full_text());
249 h.write_u16(c.span().file.0);
250 hash_scope(&mut h, c.captured());
251 h.finish()
252}
253
254pub fn hash_func(h: &mut Fingerprinter, f: &Func) {
255 match f {
256 // A native function is a fieldless enum, so its debug form is its identity.
257 Func::Native(n) => { h.write_u8(0); h.write_str(&fmt!("{:?}", n)); }
258 Func::Element(k) => { h.write_u8(1); h.write_u64(*k as u64); }
259 Func::Closure(c) => { h.write_u8(2); h.write_fingerprint(c.fingerprint()); }
260 Func::With(w) => { h.write_u8(3); hash_func(h, &w.0); hash_args(h, &w.1); }
261 #[cfg(feature = "plugin")]
262 Func::Plugin(p) => { h.write_u8(4); h.write_fingerprint(p.fingerprint()); }
263 }
264}
265
266pub fn hash_args(h: &mut Fingerprinter, a: &Args) {
267 h.write_usize(a.items.len());
268 for arg in a.items.iter() {
269 hash_opt(h, &arg.name, |h, n| h.write_str(n));
270 hash_value(h, &arg.value);
271 }
272}
273
274pub fn hash_selector(h: &mut Fingerprinter, s: &Selector) {
275 match s {
276 Selector::Elem(k, fields) => {
277 h.write_u8(0);
278 h.write_u64(*k as u64);
279 hash_opt(h, fields, |h, fs| {
280 h.write_usize(fs.len());
281 for (id, v) in fs {
282 h.write_u8(id.0);
283 hash_value(h, v);
284 }
285 });
286 }
287 Selector::Label(l) => { h.write_u8(1); h.write_str(l.as_str()); }
288 Selector::Text(t) => { h.write_u8(2); h.write_str(t); }
289 Selector::Regex(r) => { h.write_u8(3); h.write_str(&r.pattern); }
290 Selector::Location(l) => { h.write_u8(4); h.write_u64(l.0); }
291 Selector::Or(ss) => {
292 h.write_u8(5);
293 h.write_usize(ss.len());
294 for x in ss {
295 hash_selector(h, x);
296 }
297 }
298 Selector::And(ss) => {
299 h.write_u8(6);
300 h.write_usize(ss.len());
301 for x in ss {
302 hash_selector(h, x);
303 }
304 }
305 Selector::Before { selector, end, inclusive } => {
306 h.write_u8(7);
307 hash_selector(h, selector);
308 hash_selector(h, end);
309 h.write_bool(*inclusive);
310 }
311 Selector::After { selector, start, inclusive } => {
312 h.write_u8(8);
313 hash_selector(h, selector);
314 hash_selector(h, start);
315 h.write_bool(*inclusive);
316 }
317 }
318}
319
320fn hash_property(h: &mut Fingerprinter, p: &Property) {
321 h.write_u64(p.elem as u64);
322 h.write_u8(p.field.0);
323 hash_value(h, &p.value);
324 h.write_bool(p.liftable);
325 h.write_bool(p.outside);
326}
327
328fn hash_recipe(h: &mut Fingerprinter, r: &Recipe) {
329 hash_opt(h, &r.selector, hash_selector);
330 match &r.transform {
331 Transformation::Content(c) => { h.write_u8(0); h.write_fingerprint(c.fingerprint()); }
332 Transformation::Func(f) => { h.write_u8(1); hash_func(h, f); }
333 Transformation::Style(s) => { h.write_u8(2); h.write_fingerprint(s.fingerprint()); }
334 }
335 h.write_bool(r.outside);
336}
337
338pub fn hash_style(h: &mut Fingerprinter, s: &Style) {
339 match s {
340 Style::Property(p) => { h.write_u8(0); hash_property(h, p); }
341 Style::Recipe(r) => { h.write_u8(1); hash_recipe(h, r); }
342 Style::Revocation(i) => { h.write_u8(2); h.write_usize(i.0); }
343 }
344}
345
346pub fn hash_styles(h: &mut Fingerprinter, s: &Styles) {
347 h.write_usize(s.len());
348 for style in s.iter() {
349 hash_style(h, style);
350 }
351}
352
353/// Hashes a value by its structure, span-free.
354pub fn hash_value(h: &mut Fingerprinter, v: &Value) {
355 match v {
356 Value::None => h.write_u8(0),
357 Value::Auto => h.write_u8(1),
358 Value::Bool(b) => { h.write_u8(2); h.write_bool(*b); }
359 Value::Int(i) => { h.write_u8(3); h.write_i64(*i); }
360 Value::Float(f) => { h.write_u8(4); h.write_f64(*f); }
361 // A decimal holds three plain numbers, so its debug form is its value and its scale.
362 Value::Decimal(d) => { h.write_u8(5); h.write_str(&fmt!("{:?}", d)); }
363 Value::Length(l) => { h.write_u8(6); hash_length(h, l); }
364 Value::Angle(a) => { h.write_u8(7); hash_angle(h, a); }
365 Value::Ratio(r) => { h.write_u8(8); h.write_f64(r.0); }
366 Value::Relative(r) => { h.write_u8(9); h.write_f64(r.rel.0); hash_length(h, &r.abs); }
367 Value::Fraction(f) => { h.write_u8(10); h.write_f64(f.0); }
368 Value::Color(c) => { h.write_u8(11); hash_color(h, c); }
369 Value::Gradient(g) => { h.write_u8(12); hash_gradient(h, g); }
370 Value::Tiling(t) => { h.write_u8(13); hash_tiling(h, t); }
371 Value::Stroke(s) => { h.write_u8(14); hash_stroke(h, s); }
372 Value::Alignment(a) => { h.write_u8(15); hash_alignment(h, a); }
373 Value::Direction(d) => { h.write_u8(16); hash_direction(h, d); }
374 Value::Symbol(s) => { h.write_u8(17); hash_symbol(h, s); }
375 Value::Str(s) => { h.write_u8(18); h.write_str(s); }
376 Value::Bytes(b) => { h.write_u8(19); h.write_u64(b.len() as u64); h.write(b); }
377 Value::Label(l) => { h.write_u8(20); h.write_str(l.as_str()); }
378 Value::Datetime(d) => { h.write_u8(21); hash_datetime(h, d); }
379 Value::Duration(d) => { h.write_u8(22); h.write_f64(d.secs); }
380 Value::Version(parts) => {
381 h.write_u8(23);
382 h.write_usize(parts.len());
383 for p in parts.iter() {
384 h.write_u32(*p);
385 }
386 }
387 Value::Regex(r) => { h.write_u8(24); h.write_str(&r.pattern); }
388 Value::Content(c) => { h.write_u8(25); h.write_fingerprint(c.fingerprint()); }
389 Value::Array(a) => {
390 h.write_u8(26);
391 h.write_usize(a.len());
392 for x in a.iter() {
393 hash_value(h, x);
394 }
395 }
396 // A dictionary is hashed in insertion order, which is the order Typst iterates it in.
397 Value::Dict(d) => {
398 h.write_u8(27);
399 h.write_usize(d.len());
400 for (k, x) in d.iter() {
401 h.write_str(k);
402 hash_value(h, x);
403 }
404 }
405 Value::Func(f) => { h.write_u8(28); hash_func(h, f); }
406 Value::Args(a) => { h.write_u8(29); hash_args(h, a); }
407 // A module's scope is its own frame; the standard library behind it is shared and left out.
408 Value::Module(m) => {
409 h.write_u8(30);
410 h.write_str(&m.name);
411 hash_scope(h, &m.scope);
412 h.write_fingerprint(m.content.fingerprint());
413 }
414 Value::Type(t) => { h.write_u8(31); h.write_u64(*t as u64); }
415 Value::Styles(s) => { h.write_u8(32); h.write_fingerprint(s.fingerprint()); }
416 Value::Selector(s) => { h.write_u8(33); hash_selector(h, s); }
417 Value::Counter(c) => {
418 h.write_u8(34);
419 match &c.key {
420 CounterKey::Page => h.write_u8(0),
421 CounterKey::Selector(s) => { h.write_u8(1); hash_selector(h, s); }
422 CounterKey::Str(s) => { h.write_u8(2); h.write_str(s); }
423 }
424 }
425 Value::State(s) => { h.write_u8(35); h.write_str(&s.key); hash_value(h, &s.init); }
426 Value::Location(l) => { h.write_u8(36); h.write_u64(l.0); }
427 }
428}
429
430// Guards are a set, so they are written sorted.
431fn hash_guards(h: &mut Fingerprinter, guards: &[RecipeIndex]) {
432 let mut g: Vec<usize> = guards.iter().map(|i| i.0).collect();
433 g.sort_unstable();
434 h.write_usize(g.len());
435 for i in g {
436 h.write_usize(i);
437 }
438}
439
440fn hash_label(h: &mut Fingerprinter, l: &Option<Label>) {
441 hash_opt(h, l, |h, l| h.write_str(l.as_str()));
442}
443
444/// The fingerprint of an element: its kind, label, fields by id, guards and prepared flag.
445pub fn elem_fp(e: &Elem) -> Fingerprint {
446 let mut h = Fingerprinter::new();
447 h.write_u8(0);
448 h.write_u64(e.kind as u64);
449 hash_label(&mut h, &e.label);
450 let mut fields: Vec<&(FieldId, Value)> = e.fields.iter().collect();
451 fields.sort_by_key(|(id, _)| id.0);
452 h.write_usize(fields.len());
453 for (id, v) in fields {
454 h.write_u8(id.0);
455 hash_value(&mut h, v);
456 }
457 hash_guards(&mut h, &e.guards);
458 h.write_bool(e.prepared);
459 h.finish()
460}
461
462// Does the value hold content, or code that makes it? Such a field is what an edit changes.
463fn holds_content(v: &Value) -> bool {
464 match v {
465 Value::Content(_) | Value::Func(_) | Value::Args(_) | Value::Module(_) => true,
466 Value::Array(a) => a.iter().any(holds_content),
467 Value::Dict(d) => d.iter().any(|(_, x)| holds_content(x)),
468 _ => false,
469 }
470}
471
472/// The shell of an element: its kind, label and the fields that hold no content, by id. Typing into the
473/// content it holds leaves its shell as it was, so a place keyed by the shell stays where it is.
474pub fn elem_shell_fp(e: &Elem) -> Fingerprint {
475 let mut h = Fingerprinter::new();
476 h.write_u8(3);
477 h.write_u64(e.kind as u64);
478 hash_label(&mut h, &e.label);
479 let mut fields: Vec<&(FieldId, Value)> = e.fields.iter().filter(|(_, v)| !holds_content(v)).collect();
480 fields.sort_by_key(|(id, _)| id.0);
481 h.write_usize(fields.len());
482 for (id, v) in fields {
483 h.write_u8(id.0);
484 hash_value(&mut h, v);
485 }
486 h.finish()
487}
488
489/// The shell of a sequence: its label alone, since it holds nothing but children.
490pub fn seq_shell_fp(s: &Sequence) -> Fingerprint {
491 let mut h = Fingerprinter::new();
492 h.write_u8(4);
493 hash_label(&mut h, &s.label);
494 h.finish()
495}
496
497/// The shell of styled content: nothing, since it holds a child and styles over it.
498pub fn styled_shell_fp() -> Fingerprint {
499 let mut h = Fingerprinter::new();
500 h.write_u8(5);
501 h.finish()
502}
503
504/// The fingerprint of a sequence: its label, guards and children in order.
505pub fn seq_fp(s: &Sequence) -> Fingerprint {
506 let mut h = Fingerprinter::new();
507 h.write_u8(1);
508 hash_label(&mut h, &s.label);
509 hash_guards(&mut h, &s.guards);
510 h.write_usize(s.children.len());
511 for c in &s.children {
512 h.write_fingerprint(c.fingerprint());
513 }
514 h.finish()
515}
516
517/// The fingerprint of styled content: its child and its styles.
518pub fn styled_fp(s: &Styled) -> Fingerprint {
519 let mut h = Fingerprinter::new();
520 h.write_u8(2);
521 h.write_fingerprint(s.child.fingerprint());
522 h.write_fingerprint(s.styles.fingerprint());
523 h.finish()
524}
525
526/// The fingerprint of a style list.
527pub fn styles_fp(s: &Styles) -> Fingerprint {
528 let mut h = Fingerprinter::new();
529 hash_styles(&mut h, s);
530 h.finish()
531}
532
533/// A value that keeps its fingerprint in a cell of its own.
534pub trait Kept: Clone {
535 fn cell(&mut self) -> &mut LazyFingerprint;
536}
537
538/// A shared handle on a value and its fingerprint cell. Handles clone as a reference-count bump and
539/// share the cell, so a subtree is hashed once however many parents hold it. The value is readable
540/// through [`Deref`] and changeable only through [`Shared::edit`] or [`Shared::take`].
541pub struct Shared<T: Kept>(Arc<T>);
542
543impl<T: Kept> Shared<T> {
544 pub fn new(v: T) -> Self { Shared(Arc::new(v)) }
545
546 /// The value for change, copied first if another handle shares it, its fingerprint forgotten.
547 pub fn edit(&mut self) -> &mut T {
548 let v = Arc::make_mut(&mut self.0);
549 v.cell().clear();
550 v
551 }
552
553 /// The value itself, copied if another handle shares it, its fingerprint forgotten.
554 pub fn take(self) -> T {
555 let mut v = Arc::try_unwrap(self.0).unwrap_or_else(|a| (*a).clone());
556 v.cell().clear();
557 v
558 }
559
560 /// Does another handle hold the value, so that a change would copy it first?
561 pub fn is_shared(&self) -> bool { Arc::strong_count(&self.0) > 1 }
562
563 /// Do both handles share one value?
564 pub fn ptr_eq(a: &Self, b: &Self) -> bool { Arc::ptr_eq(&a.0, &b.0) }
565}
566
567impl<T: Kept> Deref for Shared<T> {
568 type Target = T;
569 fn deref(&self) -> &T { &self.0 }
570}
571
572impl<T: Kept> Clone for Shared<T> {
573 fn clone(&self) -> Self { Shared(Arc::clone(&self.0)) }
574}
575
576impl<T: Kept + Default> Default for Shared<T> {
577 fn default() -> Self { Shared::new(T::default()) }
578}
579
580// Transparent, so a handle prints as the value it holds.
581impl<T: Kept + fmt::Debug> fmt::Debug for Shared<T> {
582 fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { fmt::Debug::fmt(&*self.0, f) }
583}