git.iko.soy/j
on master help sign in
j/src/value.rs
1284 lines 45 kB history raw
1//! Values of the j language (§2).
3use crate::ast::{Expr, Pattern};
4use num_bigint::BigInt;
5use std::collections::{BTreeMap, BTreeSet, HashMap};
6use std::rc::{Rc, Weak};
8pub type RecordMap = BTreeMap<String, Value>;
10#[derive(Clone)]
11pub enum Value {
12 Int(BigInt),
13 Text(Rc<String>),
14 Bool(bool),
15 List(ListVal),
16 Record(Rc<RecordMap>),
17 Fun(Rc<FunVal>),
18 Id(Rc<String>),
19 Blob(Rc<BlobVal>),
20 Shape(Rc<ShapeVal>),
21 /// a value computed on first use (§2): currently used for a commit's
22 /// `files` list, so loading a repo does not materialize every commit's
23 /// file list. Forced transparently by `Value::field` and `value_eq`.
24 Thunk(Rc<ThunkVal>),
27/// A list: shared elements plus the offset of its first one, so dropping a
28/// prefix (`tail`, `drop`) shares the storage instead of copying it. The
29/// zipper walks — `up` is `tail repo.context`, and `top`/`ancestors` apply it
30/// once per level — made a copying `tail` quadratic in the depth of history.
31/// A tail keeps the elements before it alive; `j` is a single short run, so
32/// holding them costs nothing.
33#[derive(Clone)]
34pub struct ListVal {
35 items: Rc<Vec<Value>>,
36 start: usize,
39impl ListVal {
40 pub fn new(items: Vec<Value>) -> ListVal {
41 ListVal {
42 items: Rc::new(items),
43 start: 0,
44 }
45 }
46 /// the list without its first `n` elements, sharing the storage
47 pub fn skip(&self, n: usize) -> ListVal {
48 ListVal {
49 items: self.items.clone(),
50 start: self.items.len().min(self.start.saturating_add(n)),
51 }
52 }
53 pub fn as_slice(&self) -> &[Value] {
54 &self.items[self.start..]
55 }
56 /// which list this is, while it is held: two lists of one identity
57 /// share their elements from the same first one, so are the same list
58 /// without either being compared
59 pub fn identity(&self) -> (*const Vec<Value>, usize) {
60 (Rc::as_ptr(&self.items), self.start)
61 }
63 /// Observe the shared storage without keeping a cached list alive.
64 pub(crate) fn weak_storage(&self) -> std::rc::Weak<Vec<Value>> {
65 Rc::downgrade(&self.items)
66 }
69impl std::ops::Deref for ListVal {
70 type Target = [Value];
71 fn deref(&self) -> &[Value] {
72 self.as_slice()
73 }
76pub struct ThunkVal {
77 state: std::cell::RefCell<ThunkState>,
78 /// for a commit's `files` as the backend built them: the change id of the
79 /// stored commit whose tree this loads. An edit that changes the files
80 /// replaces the thunk, so a commit still holding the one tagged with its
81 /// own id holds exactly the stored tree — the only case in which the
82 /// backend's answers about that tree describe the value (§7.2).
83 origin: Option<String>,
84 /// for a commit's `files` as the backend built them: a name for the
85 /// stored tree this loads. Two lists loaded under the same name are
86 /// equal, and a list the backend loads from a tree is a snapshot (§7.3),
87 /// so persisting compares and validates a commit the program left as
88 /// loaded without reading its files (§7.5).
89 tree: Option<String>,
92enum ThunkState {
93 Pending(Box<dyn FnOnce() -> Result<Value, Crash>>),
94 /// the computation has been taken out of `Pending` and is running
95 Forcing,
96 Ready(Value),
97 /// the computation crashed (a store read failed). Every later force
98 /// crashes the same way (§7.2): a crash caught by `or`, or swallowed by
99 /// rendering, must not leave some other value behind.
100 Failed(Crash),
103impl std::fmt::Debug for ThunkVal {
104 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
105 match &*self.state.borrow() {
106 ThunkState::Pending(_) => write!(f, "Thunk(pending)"),
107 ThunkState::Forcing => write!(f, "Thunk(forcing)"),
108 ThunkState::Ready(v) => write!(f, "Thunk({:?})", v),
109 ThunkState::Failed(c) => write!(f, "Thunk(failed: {})", c.msg),
110 }
111 }
114impl ThunkVal {
115 pub fn new(f: impl FnOnce() -> Result<Value, Crash> + 'static) -> Self {
116 ThunkVal {
117 state: std::cell::RefCell::new(ThunkState::Pending(Box::new(f))),
118 origin: None,
119 tree: None,
120 }
121 }
123 /// the lazy `files` of the stored commit with change id `origin`, which
124 /// load the stored tree named `tree`, if the backend names its trees
125 pub fn stored(
126 origin: String,
127 tree: Option<String>,
128 f: impl FnOnce() -> Result<Value, Crash> + 'static,
129 ) -> Self {
130 ThunkVal {
131 origin: Some(origin),
132 tree,
133 ..ThunkVal::new(f)
134 }
135 }
137 /// the change id of the stored commit whose tree this loads, if any
138 pub fn origin(&self) -> Option<&str> {
139 self.origin.as_deref()
140 }
142 /// the name of the stored tree this loads, if the backend gave one
143 pub fn tree(&self) -> Option<&str> {
144 self.tree.as_deref()
145 }
147 /// the value, where it has been computed; nothing is computed here
148 pub fn peek(&self) -> Option<Value> {
149 match &*self.state.borrow() {
150 ThunkState::Ready(v) => Some(v.clone()),
151 _ => None,
152 }
153 }
155 /// the value, computing it on first call and memoizing the outcome, a
156 /// crash included
157 pub fn force(&self) -> Result<Value, Crash> {
158 match &*self.state.borrow() {
159 ThunkState::Ready(v) => return Ok(v.clone()),
160 ThunkState::Failed(c) => return Err(c.clone()),
161 ThunkState::Forcing => {
162 return Err(Crash::new("internal: a lazy value was forced re-entrantly"))
163 }
164 ThunkState::Pending(_) => {}
165 }
166 let thunk = match std::mem::replace(&mut *self.state.borrow_mut(), ThunkState::Forcing) {
167 ThunkState::Pending(t) => t,
168 _ => unreachable!("the state was Pending just above"),
169 };
170 let out = thunk();
171 *self.state.borrow_mut() = match &out {
172 Ok(v) => ThunkState::Ready(v.clone()),
173 Err(c) => ThunkState::Failed(c.clone()),
174 };
175 out
176 }
179impl Value {
180 /// force a thunk; every other value is returned unchanged
181 pub fn forced(&self) -> Result<Value, Crash> {
182 match self {
183 Value::Thunk(t) => t.force(),
184 _ => Ok(self.clone()),
185 }
186 }
189#[derive(Clone, Debug, PartialEq, Eq)]
190pub enum BlobKind {
191 Regular,
192 Executable,
193 Symlink,
196#[derive(Clone)]
197pub enum BlobContent {
198 Resolved(Rc<Vec<u8>>),
199 /// not yet read from the store; `force` reads the bytes on first use and
200 /// memoizes them. `id` is the content hash (jj FileId hex), which is
201 /// enough for equality and for persisting an unchanged blob without ever
202 /// reading its bytes.
203 Lazy(Rc<LazyBlob>),
204 /// Conflict sides, jj order: alternating adds and removes, starting and
205 /// ending with an add: [add, (remove, add)*]. For the in-memory backend:
206 /// [to, from, onto]-style three sides as [add, remove, add]. `None` is a
207 /// side on which the path is absent (a deletion conflict, §7.3).
208 Conflict(Vec<Option<ConflictSide>>),
211/// One present side of a conflict: its content and its own file type, which
212/// jj keeps per side (§7.3)
213#[derive(Clone, Debug, PartialEq, Eq)]
214pub struct ConflictSide {
215 pub kind: BlobKind,
216 pub bytes: Rc<Vec<u8>>,
217 /// a side on which jj holds a directory, in a conflict between a file
218 /// and a directory: the hex id of that tree, kept opaque so the side is
219 /// written back as the directory it was. Its `bytes` are empty (§7.3).
220 pub tree: Option<String>,
223impl ConflictSide {
224 pub fn regular(bytes: &[u8]) -> ConflictSide {
225 ConflictSide {
226 kind: BlobKind::Regular,
227 bytes: Rc::new(bytes.to_vec()),
228 tree: None,
229 }
230 }
233/// A blob whose bytes are read from the store only on first use (§7.2):
234/// building the Repo value must not inflate every file of every commit.
235pub struct LazyBlob {
236 /// content hash (jj FileId hex)
237 pub id: String,
238 state: std::cell::RefCell<LazyState>,
241enum LazyState {
242 Pending(Box<dyn FnOnce() -> Result<Rc<Vec<u8>>, Crash>>),
243 /// the read has been taken out of `Pending` and is running
244 Forcing,
245 Ready(Rc<Vec<u8>>),
246 /// the read failed: every later force fails the same way, so the blob
247 /// never reads as empty (§7.2), whoever caught or swallowed the crash
248 Failed(Crash),
251impl std::fmt::Debug for LazyBlob {
252 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
253 write!(f, "Lazy({})", self.id)
254 }
257impl std::fmt::Debug for BlobContent {
258 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
259 match self {
260 BlobContent::Resolved(b) => write!(f, "Resolved({} bytes)", b.len()),
261 BlobContent::Lazy(l) => write!(f, "{:?}", l),
262 BlobContent::Conflict(s) => write!(f, "Conflict({} sides)", s.len()),
263 }
264 }
267impl LazyBlob {
268 pub fn new(id: String, force: impl FnOnce() -> Result<Rc<Vec<u8>>, Crash> + 'static) -> Self {
269 LazyBlob {
270 id,
271 state: std::cell::RefCell::new(LazyState::Pending(Box::new(force))),
272 }
273 }
275 /// the bytes, reading from the store on first call and memoizing the
276 /// outcome, a failed read included
277 pub fn force(&self) -> Result<Rc<Vec<u8>>, Crash> {
278 // fast path: already forced
279 match &*self.state.borrow() {
280 LazyState::Ready(b) => return Ok(b.clone()),
281 LazyState::Failed(c) => return Err(c.clone()),
282 LazyState::Forcing => {
283 return Err(Crash::new("internal: a lazy blob was read re-entrantly"))
284 }
285 LazyState::Pending(_) => {}
286 }
287 let thunk = match std::mem::replace(&mut *self.state.borrow_mut(), LazyState::Forcing) {
288 LazyState::Pending(t) => t,
289 _ => unreachable!("the state was Pending just above"),
290 };
291 let out = thunk();
292 *self.state.borrow_mut() = match &out {
293 Ok(b) => LazyState::Ready(b.clone()),
294 Err(c) => LazyState::Failed(c.clone()),
295 };
296 out
297 }
300#[derive(Clone, Debug)]
301pub struct BlobVal {
302 pub kind: BlobKind,
303 pub content: BlobContent,
306impl BlobVal {
307 pub fn text_blob(s: &str) -> Value {
308 Value::Blob(Rc::new(BlobVal {
309 kind: BlobKind::Regular,
310 content: BlobContent::Resolved(Rc::new(s.as_bytes().to_vec())),
311 }))
312 }
313 pub fn is_unresolved(&self) -> bool {
314 matches!(self.content, BlobContent::Conflict(_))
315 }
316 /// size in bytes; a lazy blob reports the size of its (memoized) bytes,
317 /// forcing on first call
318 pub fn size(&self) -> usize {
319 match &self.content {
320 BlobContent::Resolved(b) => b.len(),
321 BlobContent::Lazy(l) => l.force().map(|b| b.len()).unwrap_or(0),
322 BlobContent::Conflict(sides) => sides.iter().flatten().map(|s| s.bytes.len()).sum(),
323 }
324 }
325 /// content as bytes, forcing a lazy blob; conflicts render with jj-style
326 /// conflict markers
327 pub fn bytes(&self) -> Result<Vec<u8>, Crash> {
328 match &self.content {
329 BlobContent::Resolved(b) => Ok(b.as_ref().clone()),
330 BlobContent::Lazy(l) => Ok(l.force()?.as_ref().clone()),
331 BlobContent::Conflict(sides) => Ok(render_conflict(sides)),
332 }
333 }
334 /// number of lines, counted over the bytes in place. Equivalent to
335 /// `String::from_utf8_lossy(&self.bytes()?).lines().count()` — a `\n`
336 /// byte is always a `\n` character in UTF-8, and lossy replacement never
337 /// introduces one — but without copying the content out.
338 pub fn line_count(&self) -> usize {
339 fn count(b: &[u8]) -> usize {
340 let nl = bytecount(b);
341 if b.is_empty() || b.ends_with(b"\n") {
342 nl
343 } else {
344 nl + 1
345 }
346 }
347 fn bytecount(b: &[u8]) -> usize {
348 b.iter().filter(|c| **c == b'\n').count()
349 }
350 match &self.content {
351 BlobContent::Resolved(b) => count(b),
352 BlobContent::Lazy(l) => l.force().map(|b| count(&b)).unwrap_or(1),
353 BlobContent::Conflict(sides) => count(&render_conflict(sides)),
354 }
355 }
356 /// the content hash of a lazy blob, if it is one (used to persist an
357 /// unchanged blob without reading its bytes)
358 pub fn lazy_id(&self) -> Option<&str> {
359 match &self.content {
360 BlobContent::Lazy(l) => Some(&l.id),
361 _ => None,
362 }
363 }
366/// Render a conflict with jj-style markers; a side the path is absent on
367/// renders as empty content, as jj materialises it.
368pub fn render_conflict(sides: &[Option<ConflictSide>]) -> Vec<u8> {
369 // sides: [add0, remove0, add1, remove1, ... addN]
370 let mut out = Vec::new();
371 out.extend_from_slice(b"<<<<<<<\n");
372 let mut i = 0;
373 while i < sides.len() {
374 let bytes: &[u8] = sides[i].as_ref().map_or(&[], |s| &s.bytes);
375 if i % 2 == 0 {
376 out.extend_from_slice(b"+++++++\n");
377 out.extend_from_slice(bytes);
378 ensure_newline(&mut out);
379 } else {
380 out.extend_from_slice(b"%%%%%%%\n");
381 out.extend_from_slice(bytes);
382 ensure_newline(&mut out);
383 }
384 i += 1;
385 }
386 out.extend_from_slice(b">>>>>>>\n");
387 out
390fn ensure_newline(v: &mut Vec<u8>) {
391 if !v.is_empty() && !v.ends_with(b"\n") {
392 v.push(b'\n');
393 }
396#[derive(Clone, Copy, PartialEq, Eq, Debug)]
397pub enum PrimKind {
398 Int,
399 Text,
400 Bool,
401 Id,
402 Blob,
405impl PrimKind {
406 pub fn name(&self) -> &'static str {
407 match self {
408 PrimKind::Int => "Int",
409 PrimKind::Text => "Text",
410 PrimKind::Bool => "Bool",
411 PrimKind::Id => "Id",
412 PrimKind::Blob => "Blob",
413 }
414 }
417#[derive(Clone, PartialEq, Eq, Debug)]
418pub enum ShapeKind {
419 Record(BTreeSet<String>),
420 Prim(PrimKind),
423#[derive(Clone, Debug)]
424pub struct ShapeVal {
425 pub name: String,
426 pub kind: ShapeKind,
429impl PartialEq for ShapeVal {
430 fn eq(&self, other: &Self) -> bool {
431 self.kind == other.kind
432 }
435pub type BuiltinFn = fn(&mut crate::eval::Interp, &[Value]) -> Result<Value, Crash>;
437pub enum FunVal {
438 Builtin {
439 name: String,
440 arity: usize,
441 args: Vec<Value>,
442 f: BuiltinFn,
443 /// the name this function is under, its contract as further
444 /// arguments arrive, and how many of `args` it held when it was
445 /// given that name, which are its value's, not the arguments a
446 /// signed definition was given (§5.2)
447 pending: Option<(String, Rc<crate::shape::ContractExpr>, usize)>,
448 },
449 Closure {
450 name: Option<String>, // top-level definition name, if any
451 params: Vec<Pattern>,
452 applied: usize,
453 /// the arguments supplied so far, for rendering (§5.2)
454 applied_args: Vec<Value>,
455 body: Rc<Expr>,
456 env: Env,
457 /// the lambda's source, which it renders as (§5.2)
458 src: crate::ast::Source,
459 /// contract of this function as further arguments arrive
460 pending: Option<(String, Rc<crate::shape::ContractExpr>)>,
461 },
462 /// `f or g` lifted pointwise over functions (§4.6)
463 OrFun(Value, Value),
464 /// a composition `f . g` applied as `f (g x)` (§4.9); `(.)` itself
465 /// builds a builtin node instead (builtins::compose_values)
466 ComposeLazy(Value, Value),
467 /// a label literal %name: applies as `labelled "name"`
468 Labelled(String, Value),
471/// What a function holds that may hold further functions: a closure's
472/// environment and arguments, a builtin's arguments, the operands of an
473/// `or` or a composition, a label's `labelled`. It is only ever dropped.
474#[allow(dead_code)]
475enum Held {
476 Closure(Env, Vec<Value>),
477 Args(Vec<Value>),
478 Two(Value, Value),
479 One(Value),
482/// How many function drops run inside one another before the next one's
483/// contents are put off to the outermost.
484const INLINE_FUN_DROPS: usize = 64;
486struct FunDrops {
487 depth: std::cell::Cell<usize>,
488 put_off: std::cell::RefCell<Vec<Held>>,
491thread_local! {
492 static FUN_DROPS: FunDrops = const {
493 FunDrops {
494 depth: std::cell::Cell::new(0),
495 put_off: std::cell::RefCell::new(Vec::new()),
496 }
497 };
500/// A function is dropped with what it holds, which may be a function holding
501/// a function, and so on: a closure over a closure, a composition of
502/// compositions, a named wrapper around another (named_apply). Dropped the
503/// usual way, such a chain recursed once per link on the native stack, and a
504/// chain a recursion had built a million links long aborted the process
505/// (§4.1). Past a small depth, what a function holds is put off, and the
506/// outermost function drop drops it, so the stack a drop takes is bounded.
507impl Drop for FunVal {
508 fn drop(&mut self) {
509 let held = match self {
510 FunVal::Closure {
511 env, applied_args, ..
512 } => Held::Closure(std::mem::replace(env, Env::empty()), std::mem::take(applied_args)),
513 FunVal::Builtin { args, .. } => Held::Args(std::mem::take(args)),
514 FunVal::OrFun(a, b) | FunVal::ComposeLazy(a, b) => Held::Two(
515 std::mem::replace(a, Value::Bool(false)),
516 std::mem::replace(b, Value::Bool(false)),
517 ),
518 FunVal::Labelled(_, v) => Held::One(std::mem::replace(v, Value::Bool(false))),
519 };
520 // once the thread's locals are gone, `held` simply drops here
521 let _ = FUN_DROPS.try_with(move |d| {
522 let depth = d.depth.get();
523 if depth >= INLINE_FUN_DROPS {
524 d.put_off.borrow_mut().push(held);
525 return;
526 }
527 d.depth.set(depth + 1);
528 drop(held);
529 if depth == 0 {
530 loop {
531 let next = d.put_off.borrow_mut().pop();
532 match next {
533 Some(h) => drop(h),
534 None => break,
535 }
536 }
537 }
538 d.depth.set(depth);
539 });
540 }
543impl Value {
544 pub fn kind_name(&self) -> &'static str {
545 match self {
546 Value::Int(_) => "Int",
547 Value::Text(_) => "Text",
548 Value::Bool(_) => "Bool",
549 Value::List(_) => "list",
550 Value::Record(_) => "record",
551 Value::Fun(_) => "function",
552 Value::Id(_) => "Id",
553 Value::Blob(_) => "Blob",
554 Value::Shape(_) => "Shape",
555 // a thunk stands in for its eventual value (currently a list of
556 // file entries); kind_name is used in error messages
557 Value::Thunk(_) => "list",
558 }
559 }
561 pub fn record(fields: &[(&str, Value)]) -> Value {
562 let mut m = RecordMap::new();
563 for (k, v) in fields {
564 m.insert(k.to_string(), v.clone());
565 }
566 Value::Record(Rc::new(m))
567 }
569 pub fn field(&self, name: &str) -> Result<Value, Crash> {
570 match self {
571 Value::Record(m) => m
572 .get(name)
573 .cloned()
574 .ok_or_else(|| Crash::new(format!("record has no field `{}`", name)))
575 .and_then(|v| v.forced()),
576 _ => Err(Crash::new(format!(
577 "cannot select field `{}` from a {}",
578 name,
579 self.kind_name()
580 ))),
581 }
582 }
584 pub fn field_set(&self) -> Option<BTreeSet<String>> {
585 match self {
586 Value::Record(m) => Some(m.keys().cloned().collect()),
587 _ => None,
588 }
589 }
591 pub fn as_list(&self) -> Result<&[Value], Crash> {
592 match self {
593 Value::List(xs) => Ok(xs.as_slice()),
594 _ => Err(Crash::new(format!("expected a list, got a {}", self.kind_name()))),
595 }
596 }
598 pub fn as_text(&self) -> Result<&str, Crash> {
599 match self {
600 Value::Text(t) => Ok(t),
601 _ => Err(Crash::new(format!("expected Text, got a {}", self.kind_name()))),
602 }
603 }
605 pub fn as_int(&self) -> Result<&BigInt, Crash> {
606 match self {
607 Value::Int(n) => Ok(n),
608 _ => Err(Crash::new(format!("expected Int, got a {}", self.kind_name()))),
609 }
610 }
612 pub fn text(s: impl Into<String>) -> Value {
613 Value::Text(Rc::new(s.into()))
614 }
616 pub fn int(n: i64) -> Value {
617 Value::Int(BigInt::from(n))
618 }
620 pub fn list(xs: Vec<Value>) -> Value {
621 Value::List(ListVal::new(xs))
622 }
624 pub fn bool(b: bool) -> Value {
625 Value::Bool(b)
626 }
629/// Attach a definition name and contract to a function value (§4.13).
630pub fn attach_pending(v: &Value, name: &str, contract: Rc<crate::shape::Contract>) -> Value {
631 let cexpr = Rc::new(crate::shape::ContractExpr::Known { contract, at: 0 });
632 let pending = Some((name.to_string(), cexpr.clone()));
633 match v {
634 Value::Fun(fv) => match fv.as_ref() {
635 FunVal::Closure {
636 params,
637 applied,
638 body,
639 env,
640 src,
641 ..
642 } => Value::Fun(Rc::new(FunVal::Closure {
643 name: Some(name.to_string()),
644 params: params.clone(),
645 applied: *applied,
646 // the definition renders as its name, followed only by the
647 // arguments it is given, not those its value holds: `prev`,
648 // not `prev (parents)` (§5.2)
649 applied_args: Vec::new(),
650 body: body.clone(),
651 env: env.clone(),
652 src: src.clone(),
653 pending,
654 })),
655 FunVal::Builtin {
656 name: bname,
657 arity,
658 args,
659 f,
660 ..
661 } => Value::Fun(Rc::new(FunVal::Builtin {
662 name: bname.clone(),
663 arity: *arity,
664 args: args.clone(),
665 f: *f,
666 // the arguments it holds now are its value's, and those
667 // after them the definition's own: `k3 ((+)) 0` with
668 // `k3 = foldl`, past a signature that ends in a type
669 // variable and so stops counting (§5.2)
670 pending: Some((name.to_string(), cexpr, args.len())),
671 })),
672 // `f or g` and `%name` have nowhere to hold a contract, so the
673 // definition becomes `\x -> v x` under its name, which the
674 // closure machinery checks at every argument the signature lists
675 // and at the result. The check is around the lifted `or` as a
676 // whole (§4.6): a result that violates the signature is a crash,
677 // not a reason to try the other side.
678 FunVal::OrFun(_, _) | FunVal::ComposeLazy(_, _) | FunVal::Labelled(_, _) => {
679 named_apply(v.clone(), Vec::new(), name, cexpr)
680 }
681 },
682 _ => v.clone(),
683 }
686/// `\x -> f x` under a definition's name and contract: it renders as the
687/// name followed by `applied_args` (§5.2), and its further arguments and its
688/// result are checked against the contract (§4.13)
689pub fn named_apply(
690 f: Value,
691 applied_args: Vec<Value>,
692 name: &str,
693 cexpr: Rc<crate::shape::ContractExpr>,
694) -> Value {
695 Value::Fun(Rc::new(FunVal::Closure {
696 name: Some(name.to_string()),
697 params: vec![Pattern::Var("x".to_string())],
698 applied: 0,
699 applied_args,
700 body: NAMED_APPLY_BODY.with(Rc::clone),
701 env: Env::empty().extend(vec![("f".to_string(), f)]),
702 // a named closure renders by its name, not its source (§5.2)
703 src: crate::ast::Source::new(Rc::from(""), 0, 0),
704 pending: Some((name.to_string(), cexpr)),
705 }))
708thread_local! {
709 /// `f x`, the body every named_apply wrapper shares, by which one is
710 /// told from a lambda written in the language
711 static NAMED_APPLY_BODY: Rc<Expr> = {
712 let var = |n: &str| Rc::new(Expr::Var(n.to_string()));
713 Rc::new(Expr::App(var("f"), var("x")))
714 };
717/// The function `v` wraps when it is a named_apply wrapper under `name` and a
718/// contract the same as `cexpr`. Naming that function afresh under them
719/// checks all the wrapper would, so a definition that names the value of its
720/// own recursive call wraps it once, not once per call (§4.13).
721pub fn named_inner(v: &Value, name: &str, cexpr: &crate::shape::ContractExpr) -> Option<Value> {
722 match v {
723 Value::Fun(fv) => match fv.as_ref() {
724 FunVal::Closure {
725 body,
726 env,
727 pending: Some((n, c)),
728 ..
729 } if n == name
730 && c.same_as(cexpr)
731 && NAMED_APPLY_BODY.with(|b| Rc::ptr_eq(b, body)) =>
732 {
733 env.lookup("f")
734 }
735 _ => None,
736 },
737 _ => None,
738 }
741/// A crash (§4.7).
742#[derive(Debug, Clone)]
743pub struct Crash {
744 pub msg: String,
745 /// innermost base definition executing, if any
746 pub def: Option<String>,
749impl Crash {
750 pub fn new(msg: impl Into<String>) -> Crash {
751 Crash {
752 msg: msg.into(),
753 def: None,
754 }
755 }
758// ----------------------------------------------------------------------
759// Environments (persistent, for closures)
760// ----------------------------------------------------------------------
762#[derive(Clone)]
763pub struct Env {
764 frame: Option<Rc<Frame>>,
767/// A large acyclic let or a collected recursive cycle can release a long
768/// chain of parent frames. Release unique frames iteratively, keeping the
769/// next parent alive while its child's values drop, so closures capturing
770/// earlier frames cannot recurse down that chain either (§4.1).
771impl Drop for Env {
772 fn drop(&mut self) {
773 let mut next = self.frame.take();
774 while let Some(frame) = next {
775 match Rc::try_unwrap(frame) {
776 Ok(mut frame) => next = frame.parent.frame.take(),
777 Err(_) => break,
778 }
779 }
780 }
783pub struct Frame {
784 kind: FrameKind,
785 parent: Env,
788enum FrameKind {
789 Small(Vec<(String, Value)>),
790 Big(HashMap<String, Value>),
791 /// recursive let bindings: the names the block binds, and their values
792 /// in that order, filled incrementally and read through the cell so
793 /// closures capturing the frame see later bindings (§4.1)
794 Rec(Rc<[String]>, Rc<std::cell::RefCell<Vec<Value>>>),
797impl Env {
798 pub fn empty() -> Env {
799 Env { frame: None }
800 }
802 pub fn with_globals(globals: HashMap<String, Value>) -> Env {
803 Env {
804 frame: Some(Rc::new(Frame {
805 kind: FrameKind::Big(globals),
806 parent: Env::empty(),
807 })),
808 }
809 }
811 pub fn extend(&self, bindings: Vec<(String, Value)>) -> Env {
812 Env {
813 frame: Some(Rc::new(Frame {
814 kind: FrameKind::Small(bindings),
815 parent: self.clone(),
816 })),
817 }
818 }
820 /// extend with a recursive frame (for `let` blocks) binding `names`,
821 /// whose values are pushed to the returned cell in the same order
822 pub fn extend_rec(&self, names: Rc<[String]>) -> (Env, Rc<std::cell::RefCell<Vec<Value>>>) {
823 // Collect before allocating: `self` and all values the evaluator is
824 // using are still ordinary strong roots during this check.
825 maybe_collect_cycles();
826 let cell = Rc::new(std::cell::RefCell::new(Vec::with_capacity(names.len())));
827 let frame = Rc::new(Frame {
828 kind: FrameKind::Rec(names, cell.clone()),
829 parent: self.clone(),
830 });
831 RECURSIVE_FRAMES.with(|registry| {
832 let mut registry = registry.borrow_mut();
833 registry.frames.push(Rc::downgrade(&frame));
834 registry.allocations += 1;
835 });
836 (Env { frame: Some(frame) }, cell)
837 }
839 pub fn lookup(&self, name: &str) -> Option<Value> {
840 let mut cur = self.frame.as_ref();
841 while let Some(f) = cur {
842 match &f.kind {
843 FrameKind::Small(bs) => {
844 for (n, v) in bs.iter().rev() {
845 if n == name {
846 return Some(v.clone());
847 }
848 }
849 }
850 FrameKind::Rec(names, cell) => {
851 // the frame binds its names before it holds their values:
852 // one not evaluated yet is unbound here, not a same-named
853 // definition further out, which config.j's binders may
854 // reuse (§4.2)
855 if let Some(i) = names.iter().rposition(|n| n == name) {
856 return cell.borrow().get(i).cloned();
857 }
858 }
859 FrameKind::Big(m) => {
860 if let Some(v) = m.get(name) {
861 return Some(v.clone());
862 }
863 }
864 }
865 cur = f.parent.frame.as_ref();
866 }
867 None
868 }
870 /// True if this environment captures anything beyond the globals frame
871 /// (i.e. the closure was created inside a lambda/let body).
872 pub fn is_closure_capture(&self) -> bool {
873 let mut cur = self.frame.as_ref();
874 let mut small_frames = 0;
875 while let Some(f) = cur {
876 match &f.kind {
877 FrameKind::Small(_) => small_frames += 1,
878 FrameKind::Big(_) | FrameKind::Rec(..) => {}
879 }
880 cur = f.parent.frame.as_ref();
881 }
882 small_frames > 0
883 }
885 pub fn names(&self, out: &mut BTreeSet<String>) {
886 let mut cur = self.frame.as_ref();
887 while let Some(f) = cur {
888 match &f.kind {
889 FrameKind::Small(bs) => {
890 for (n, _) in bs {
891 out.insert(n.clone());
892 }
893 }
894 FrameKind::Rec(names, _) => {
895 for n in names.iter() {
896 out.insert(n.clone());
897 }
898 }
899 FrameKind::Big(m) => {
900 for n in m.keys() {
901 out.insert(n.clone());
902 }
903 }
904 }
905 cur = f.parent.frame.as_ref();
906 }
907 }
910// A recursive environment owns its bindings, and a closure in those bindings
911// may own the environment again. Weak captures would lose an escaping
912// closure's bindings, so these are real strong references. Collect their
913// unreachable cycles by subtracting the references inside their owned graph
914// from each node's reference count. References from outside that graph are
915// roots: returned values, the interpreter, and the running machine's states
916// and continuations. No explicit evaluator root stack is needed.
917//
918// Only recursive frames can introduce cycles in language values. The
919// registry is weak, and all traversal and marking below use explicit work
920// lists, including through shared lists, records, and function wrappers.
921#[derive(Default)]
922struct RecursiveFrames {
923 frames: Vec<Weak<Frame>>,
924 allocations: usize,
925 next_collection: usize,
926 without_environments: HashMap<(u8, usize), EnvironmentFree>,
927 cached_since_pruning: usize,
928 collecting: bool,
931thread_local! {
932 static RECURSIVE_FRAMES: std::cell::RefCell<RecursiveFrames> =
933 std::cell::RefCell::new(RecursiveFrames::default());
936const MIN_CYCLE_BATCH: usize = 256;
938fn maybe_collect_cycles() {
939 let due = RECURSIVE_FRAMES.with(|registry| {
940 let registry = registry.borrow();
941 !registry.collecting
942 && registry.allocations >= registry.next_collection.max(MIN_CYCLE_BATCH)
943 });
944 if due {
945 collect_cycles();
946 }
949/// Reclaim dead recursive environments. The caller must retain any result
950/// it wants to return while this runs, as an ordinary strong reference.
951pub(crate) fn collect_cycles() {
952 RECURSIVE_FRAMES.with(|shared| {
953 let mut registry = {
954 let mut registry = shared.borrow_mut();
955 if registry.collecting { return; }
956 let previous = std::mem::take(&mut *registry);
957 registry.collecting = true;
958 previous
959 };
960 // Do not hold the registry borrow while dropping values. Opaque
961 // Rust backend captures can run destructors that allocate frames or
962 // drop another interpreter; such nested collections are deferred.
963 let mut graph = CycleGraph::default();
964 for frame in &registry.frames {
965 if let Some(frame) = frame.upgrade() {
966 graph.add(CycleNode::Frame(frame));
967 }
968 }
969 graph.trace(&registry.without_environments);
970 registry.cached_since_pruning += graph.cache_environment_free(&mut registry.without_environments);
971 graph.collect();
972 // Release the collector's temporary roots before pruning the weak
973 // registry. Live recursive frames set the next batch size so a
974 // growing set of escaping closures costs amortized linear work.
975 drop(graph);
976 registry.frames.retain(|frame| frame.strong_count() != 0);
977 registry.allocations = 0;
978 registry.next_collection = registry.frames.len().max(MIN_CYCLE_BATCH);
979 // Immutable repository trees usually hold no functions. Remember
980 // that once, without keeping their values alive. Pruning is batched
981 // too: a large, live tree must not be scanned on every collection.
982 if registry.frames.is_empty() {
983 registry.without_environments.clear();
984 registry.cached_since_pruning = 0;
985 } else if registry.cached_since_pruning >=
986 (registry.without_environments.len() / 2).max(MIN_CYCLE_BATCH)
987 {
988 registry.without_environments.retain(|_, cached| cached.is_alive());
989 registry.cached_since_pruning = 0;
990 }
991 let mut pending = shared.borrow_mut();
992 registry.frames.append(&mut pending.frames);
993 registry.allocations += pending.allocations;
994 *pending = registry;
995 });
998// These containers are immutable while shared. Weak references both avoid
999// extending their lives and prevent address reuse from giving a false hit.
1000// Rc::make_mut dissociates weak pointers before it can change a container.
1001enum EnvironmentFree {
1002 List(Weak<Vec<Value>>),
1003 Record(Weak<RecordMap>),
1006impl EnvironmentFree {
1007 fn is_alive(&self) -> bool {
1008 match self {
1009 Self::List(v) => v.strong_count() != 0,
1010 Self::Record(v) => v.strong_count() != 0,
1015enum CycleNode {
1016 Frame(Rc<Frame>),
1017 Bindings(Rc<std::cell::RefCell<Vec<Value>>>),
1018 Function(Rc<FunVal>),
1019 List(Rc<Vec<Value>>),
1020 Record(Rc<RecordMap>),
1023impl CycleNode {
1024 fn key(&self) -> (u8, usize) {
1025 match self {
1026 Self::Frame(v) => (0, Rc::as_ptr(v) as usize),
1027 Self::Bindings(v) => (1, Rc::as_ptr(v) as usize),
1028 Self::Function(v) => (2, Rc::as_ptr(v) as usize),
1029 Self::List(v) => (3, Rc::as_ptr(v) as usize),
1030 Self::Record(v) => (4, Rc::as_ptr(v) as usize),
1034 fn strong_count(&self) -> usize {
1035 match self {
1036 Self::Frame(v) => Rc::strong_count(v),
1037 Self::Bindings(v) => Rc::strong_count(v),
1038 Self::Function(v) => Rc::strong_count(v),
1039 Self::List(v) => Rc::strong_count(v),
1040 Self::Record(v) => Rc::strong_count(v),
1044 fn children(&self) -> Vec<CycleNode> {
1045 let mut out = Vec::new();
1046 let mut value = |v: &Value| match v {
1047 Value::Fun(f) => out.push(Self::Function(f.clone())),
1048 // A list view owns its whole backing vector, including the
1049 // prefix that `tail`/`drop` no longer exposes.
1050 Value::List(xs) => out.push(Self::List(xs.items.clone())),
1051 Value::Record(fields) => out.push(Self::Record(fields.clone())),
1052 // Backend thunks are opaque Rust closures. Their references,
1053 // if any, remain external roots; never guess what they own.
1054 _ => {}
1055 };
1056 match self {
1057 Self::Frame(frame) => {
1058 match &frame.kind {
1059 FrameKind::Small(bindings) => {
1060 for (_, v) in bindings { value(v); }
1062 FrameKind::Big(bindings) => {
1063 for v in bindings.values() { value(v); }
1065 FrameKind::Rec(_, bindings) => {
1066 out.push(Self::Bindings(bindings.clone()));
1069 if let Some(parent) = &frame.parent.frame {
1070 out.push(Self::Frame(parent.clone()));
1073 Self::Bindings(bindings) => {
1074 for v in bindings.borrow().iter() { value(v); }
1076 Self::Function(f) => {
1077 match f.as_ref() {
1078 FunVal::Closure { env, applied_args, .. } => {
1079 for v in applied_args { value(v); }
1080 if let Some(frame) = &env.frame {
1081 out.push(Self::Frame(frame.clone()));
1084 FunVal::Builtin { args, .. } => {
1085 for v in args { value(v); }
1087 FunVal::OrFun(a, b) | FunVal::ComposeLazy(a, b) => {
1088 value(a);
1089 value(b);
1091 FunVal::Labelled(_, f) => value(f),
1094 Self::List(items) => {
1095 for v in items.iter() { value(v); }
1097 Self::Record(fields) => {
1098 for v in fields.values() { value(v); }
1101 out
1105#[derive(Default)]
1106struct CycleGraph {
1107 // Exactly one temporary strong reference per node. All temporary edge
1108 // clones are consumed by `add` before reference counts are examined.
1109 nodes: Vec<CycleNode>,
1110 indices: HashMap<(u8, usize), usize>,
1111 edges: Vec<Vec<usize>>,
1112 incoming: Vec<usize>,
1115impl CycleGraph {
1116 fn add(&mut self, node: CycleNode) -> usize {
1117 let key = node.key();
1118 if let Some(&index) = self.indices.get(&key) {
1119 return index;
1121 let index = self.nodes.len();
1122 self.indices.insert(key, index);
1123 self.nodes.push(node);
1124 self.edges.push(Vec::new());
1125 self.incoming.push(0);
1126 index
1129 fn trace(&mut self, without_environments: &HashMap<(u8, usize), EnvironmentFree>) {
1130 let mut index = 0;
1131 while index < self.nodes.len() {
1132 for child in self.nodes[index].children() {
1133 if without_environments.contains_key(&child.key()) {
1134 continue;
1136 let next = self.add(child);
1137 self.edges[index].push(next);
1138 self.incoming[next] += 1;
1140 index += 1;
1144 fn cache_environment_free(&self, cache: &mut HashMap<(u8, usize), EnvironmentFree>) -> usize {
1145 let mut parents = vec![Vec::new(); self.nodes.len()];
1146 for (index, edges) in self.edges.iter().enumerate() {
1147 for &next in edges { parents[next].push(index); }
1149 let mut reaches_frame = vec![false; self.nodes.len()];
1150 let mut work = Vec::new();
1151 for (index, node) in self.nodes.iter().enumerate() {
1152 if matches!(node, CycleNode::Frame(_)) {
1153 reaches_frame[index] = true;
1154 work.push(index);
1157 while let Some(index) = work.pop() {
1158 for &parent in &parents[index] {
1159 if !reaches_frame[parent] {
1160 reaches_frame[parent] = true;
1161 work.push(parent);
1165 let mut added = 0;
1166 for (index, node) in self.nodes.iter().enumerate() {
1167 if !reaches_frame[index] {
1168 let cached = match node {
1169 CycleNode::List(v) => EnvironmentFree::List(Rc::downgrade(v)),
1170 CycleNode::Record(v) => EnvironmentFree::Record(Rc::downgrade(v)),
1171 _ => continue,
1172 };
1173 if cache.insert(node.key(), cached).is_none() { added += 1; }
1176 added
1179 fn collect(&self) {
1180 let mut reachable = vec![false; self.nodes.len()];
1181 let mut work = Vec::new();
1182 for (index, node) in self.nodes.iter().enumerate() {
1183 if node.strong_count() > self.incoming[index] + 1 {
1184 reachable[index] = true;
1185 work.push(index);
1188 while let Some(index) = work.pop() {
1189 for &next in &self.edges[index] {
1190 if !reachable[next] {
1191 reachable[next] = true;
1192 work.push(next);
1196 for (index, node) in self.nodes.iter().enumerate() {
1197 if !reachable[index] {
1198 if let CycleNode::Bindings(bindings) = node {
1199 bindings.borrow_mut().clear();
1206// ----------------------------------------------------------------------
1207// structural equality (§4.5); comparing functions is a crash
1208// ----------------------------------------------------------------------
1210pub fn value_eq(a: &Value, b: &Value) -> Result<bool, Crash> {
1211 // force thunks at the boundary so callers never see them
1212 if let Value::Thunk(_) = a {
1213 return value_eq(&a.forced()?, b);
1215 if let Value::Thunk(_) = b {
1216 return value_eq(a, &b.forced()?);
1218 Ok(match (a, b) {
1219 (Value::Int(x), Value::Int(y)) => x == y,
1220 (Value::Text(x), Value::Text(y)) => x == y,
1221 (Value::Bool(x), Value::Bool(y)) => x == y,
1222 (Value::Id(x), Value::Id(y)) => x == y,
1223 (Value::List(x), Value::List(y)) => {
1224 if x.len() != y.len() {
1225 return Ok(false);
1227 for (u, v) in x.iter().zip(y.iter()) {
1228 if !value_eq(u, v)? {
1229 return Ok(false);
1232 true
1234 (Value::Record(x), Value::Record(y)) => {
1235 if x.len() != y.len() {
1236 return Ok(false);
1238 for ((k1, v1), (k2, v2)) in x.iter().zip(y.iter()) {
1239 if k1 != k2 || !value_eq(v1, v2)? {
1240 return Ok(false);
1243 true
1245 (Value::Blob(x), Value::Blob(y)) => {
1246 x.kind == y.kind && blob_content_eq(&x.content, &y.content)?
1248 (Value::Shape(x), Value::Shape(y)) => x == y,
1249 (Value::Fun(_), Value::Fun(_)) => {
1250 return Err(Crash::new("cannot compare functions for equality"))
1252 _ => false,
1253 })
1256/// content equality; two lazy blobs compare by content hash, without forcing
1257fn blob_content_eq(a: &BlobContent, b: &BlobContent) -> Result<bool, Crash> {
1258 Ok(match (a, b) {
1259 (BlobContent::Resolved(x), BlobContent::Resolved(y)) => x == y,
1260 (BlobContent::Lazy(x), BlobContent::Lazy(y)) => x.id == y.id,
1261 (BlobContent::Lazy(x), BlobContent::Resolved(y))
1262 | (BlobContent::Resolved(y), BlobContent::Lazy(x)) => x.force()? == *y,
1263 (BlobContent::Conflict(x), BlobContent::Conflict(y)) => x == y,
1264 _ => false,
1265 })
1268impl std::fmt::Debug for Value {
1269 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
1270 // cheap debug rendering without an interpreter
1271 match self {
1272 Value::Int(n) => write!(f, "Int({})", n),
1273 Value::Text(t) => write!(f, "Text({:?})", t),
1274 Value::Bool(b) => write!(f, "Bool({})", b),
1275 Value::Id(i) => write!(f, "Id(@{})", i),
1276 Value::List(xs) => f.debug_list().entries(xs.iter()).finish(),
1277 Value::Record(m) => f.debug_map().entries(m.iter()).finish(),
1278 Value::Fun(_) => write!(f, "Fun(..)"),
1279 Value::Blob(b) => write!(f, "Blob({:?})", b),
1280 Value::Shape(s) => write!(f, "Shape({})", s.name),
1281 Value::Thunk(t) => write!(f, "{:?}", t),