git.iko.soy/j
on codex/command-discovery help sign in
j/src/value.rs
963 lines 33 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;
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 }
64impl std::ops::Deref for ListVal {
65 type Target = [Value];
66 fn deref(&self) -> &[Value] {
67 self.as_slice()
68 }
71pub struct ThunkVal {
72 state: std::cell::RefCell<ThunkState>,
73 /// for a commit's `files` as the backend built them: the change id of the
74 /// stored commit whose tree this loads. An edit that changes the files
75 /// replaces the thunk, so a commit still holding the one tagged with its
76 /// own id holds exactly the stored tree — the only case in which the
77 /// backend's answers about that tree describe the value (§7.2).
78 origin: Option<String>,
79 /// for a commit's `files` as the backend built them: a name for the
80 /// stored tree this loads. Two lists loaded under the same name are
81 /// equal, and a list the backend loads from a tree is a snapshot (§7.3),
82 /// so persisting compares and validates a commit the program left as
83 /// loaded without reading its files (§7.5).
84 tree: Option<String>,
87enum ThunkState {
88 Pending(Box<dyn FnOnce() -> Result<Value, Crash>>),
89 /// the computation has been taken out of `Pending` and is running
90 Forcing,
91 Ready(Value),
92 /// the computation crashed (a store read failed). Every later force
93 /// crashes the same way (§7.2): a crash caught by `or`, or swallowed by
94 /// rendering, must not leave some other value behind.
95 Failed(Crash),
98impl std::fmt::Debug for ThunkVal {
99 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
100 match &*self.state.borrow() {
101 ThunkState::Pending(_) => write!(f, "Thunk(pending)"),
102 ThunkState::Forcing => write!(f, "Thunk(forcing)"),
103 ThunkState::Ready(v) => write!(f, "Thunk({:?})", v),
104 ThunkState::Failed(c) => write!(f, "Thunk(failed: {})", c.msg),
105 }
106 }
109impl ThunkVal {
110 pub fn new(f: impl FnOnce() -> Result<Value, Crash> + 'static) -> Self {
111 ThunkVal {
112 state: std::cell::RefCell::new(ThunkState::Pending(Box::new(f))),
113 origin: None,
114 tree: None,
115 }
116 }
118 /// the lazy `files` of the stored commit with change id `origin`, which
119 /// load the stored tree named `tree`, if the backend names its trees
120 pub fn stored(
121 origin: String,
122 tree: Option<String>,
123 f: impl FnOnce() -> Result<Value, Crash> + 'static,
124 ) -> Self {
125 ThunkVal {
126 origin: Some(origin),
127 tree,
128 ..ThunkVal::new(f)
129 }
130 }
132 /// the change id of the stored commit whose tree this loads, if any
133 pub fn origin(&self) -> Option<&str> {
134 self.origin.as_deref()
135 }
137 /// the name of the stored tree this loads, if the backend gave one
138 pub fn tree(&self) -> Option<&str> {
139 self.tree.as_deref()
140 }
142 /// the value, where it has been computed; nothing is computed here
143 pub fn peek(&self) -> Option<Value> {
144 match &*self.state.borrow() {
145 ThunkState::Ready(v) => Some(v.clone()),
146 _ => None,
147 }
148 }
150 /// the value, computing it on first call and memoizing the outcome, a
151 /// crash included
152 pub fn force(&self) -> Result<Value, Crash> {
153 match &*self.state.borrow() {
154 ThunkState::Ready(v) => return Ok(v.clone()),
155 ThunkState::Failed(c) => return Err(c.clone()),
156 ThunkState::Forcing => {
157 return Err(Crash::new("internal: a lazy value was forced re-entrantly"))
158 }
159 ThunkState::Pending(_) => {}
160 }
161 let thunk = match std::mem::replace(&mut *self.state.borrow_mut(), ThunkState::Forcing) {
162 ThunkState::Pending(t) => t,
163 _ => unreachable!("the state was Pending just above"),
164 };
165 let out = thunk();
166 *self.state.borrow_mut() = match &out {
167 Ok(v) => ThunkState::Ready(v.clone()),
168 Err(c) => ThunkState::Failed(c.clone()),
169 };
170 out
171 }
174impl Value {
175 /// force a thunk; every other value is returned unchanged
176 pub fn forced(&self) -> Result<Value, Crash> {
177 match self {
178 Value::Thunk(t) => t.force(),
179 _ => Ok(self.clone()),
180 }
181 }
184#[derive(Clone, Debug, PartialEq, Eq)]
185pub enum BlobKind {
186 Regular,
187 Executable,
188 Symlink,
191#[derive(Clone)]
192pub enum BlobContent {
193 Resolved(Rc<Vec<u8>>),
194 /// not yet read from the store; `force` reads the bytes on first use and
195 /// memoizes them. `id` is the content hash (jj FileId hex), which is
196 /// enough for equality and for persisting an unchanged blob without ever
197 /// reading its bytes.
198 Lazy(Rc<LazyBlob>),
199 /// Conflict sides, jj order: alternating adds and removes, starting and
200 /// ending with an add: [add, (remove, add)*]. For the in-memory backend:
201 /// [to, from, onto]-style three sides as [add, remove, add]. `None` is a
202 /// side on which the path is absent (a deletion conflict, §7.3).
203 Conflict(Vec<Option<ConflictSide>>),
206/// One present side of a conflict: its content and its own file type, which
207/// jj keeps per side (§7.3)
208#[derive(Clone, Debug, PartialEq, Eq)]
209pub struct ConflictSide {
210 pub kind: BlobKind,
211 pub bytes: Rc<Vec<u8>>,
212 /// a side on which jj holds a directory, in a conflict between a file
213 /// and a directory: the hex id of that tree, kept opaque so the side is
214 /// written back as the directory it was. Its `bytes` are empty (§7.3).
215 pub tree: Option<String>,
218impl ConflictSide {
219 pub fn regular(bytes: &[u8]) -> ConflictSide {
220 ConflictSide {
221 kind: BlobKind::Regular,
222 bytes: Rc::new(bytes.to_vec()),
223 tree: None,
224 }
225 }
228/// A blob whose bytes are read from the store only on first use (§7.2):
229/// building the Repo value must not inflate every file of every commit.
230pub struct LazyBlob {
231 /// content hash (jj FileId hex)
232 pub id: String,
233 state: std::cell::RefCell<LazyState>,
236enum LazyState {
237 Pending(Box<dyn FnOnce() -> Result<Rc<Vec<u8>>, Crash>>),
238 /// the read has been taken out of `Pending` and is running
239 Forcing,
240 Ready(Rc<Vec<u8>>),
241 /// the read failed: every later force fails the same way, so the blob
242 /// never reads as empty (§7.2), whoever caught or swallowed the crash
243 Failed(Crash),
246impl std::fmt::Debug for LazyBlob {
247 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
248 write!(f, "Lazy({})", self.id)
249 }
252impl std::fmt::Debug for BlobContent {
253 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
254 match self {
255 BlobContent::Resolved(b) => write!(f, "Resolved({} bytes)", b.len()),
256 BlobContent::Lazy(l) => write!(f, "{:?}", l),
257 BlobContent::Conflict(s) => write!(f, "Conflict({} sides)", s.len()),
258 }
259 }
262impl LazyBlob {
263 pub fn new(id: String, force: impl FnOnce() -> Result<Rc<Vec<u8>>, Crash> + 'static) -> Self {
264 LazyBlob {
265 id,
266 state: std::cell::RefCell::new(LazyState::Pending(Box::new(force))),
267 }
268 }
270 /// the bytes, reading from the store on first call and memoizing the
271 /// outcome, a failed read included
272 pub fn force(&self) -> Result<Rc<Vec<u8>>, Crash> {
273 // fast path: already forced
274 match &*self.state.borrow() {
275 LazyState::Ready(b) => return Ok(b.clone()),
276 LazyState::Failed(c) => return Err(c.clone()),
277 LazyState::Forcing => {
278 return Err(Crash::new("internal: a lazy blob was read re-entrantly"))
279 }
280 LazyState::Pending(_) => {}
281 }
282 let thunk = match std::mem::replace(&mut *self.state.borrow_mut(), LazyState::Forcing) {
283 LazyState::Pending(t) => t,
284 _ => unreachable!("the state was Pending just above"),
285 };
286 let out = thunk();
287 *self.state.borrow_mut() = match &out {
288 Ok(b) => LazyState::Ready(b.clone()),
289 Err(c) => LazyState::Failed(c.clone()),
290 };
291 out
292 }
295#[derive(Clone, Debug)]
296pub struct BlobVal {
297 pub kind: BlobKind,
298 pub content: BlobContent,
301impl BlobVal {
302 pub fn text_blob(s: &str) -> Value {
303 Value::Blob(Rc::new(BlobVal {
304 kind: BlobKind::Regular,
305 content: BlobContent::Resolved(Rc::new(s.as_bytes().to_vec())),
306 }))
307 }
308 pub fn is_unresolved(&self) -> bool {
309 matches!(self.content, BlobContent::Conflict(_))
310 }
311 /// size in bytes; a lazy blob reports the size of its (memoized) bytes,
312 /// forcing on first call
313 pub fn size(&self) -> usize {
314 match &self.content {
315 BlobContent::Resolved(b) => b.len(),
316 BlobContent::Lazy(l) => l.force().map(|b| b.len()).unwrap_or(0),
317 BlobContent::Conflict(sides) => sides.iter().flatten().map(|s| s.bytes.len()).sum(),
318 }
319 }
320 /// content as bytes, forcing a lazy blob; conflicts render with jj-style
321 /// conflict markers
322 pub fn bytes(&self) -> Result<Vec<u8>, Crash> {
323 match &self.content {
324 BlobContent::Resolved(b) => Ok(b.as_ref().clone()),
325 BlobContent::Lazy(l) => Ok(l.force()?.as_ref().clone()),
326 BlobContent::Conflict(sides) => Ok(render_conflict(sides)),
327 }
328 }
329 /// number of lines, counted over the bytes in place. Equivalent to
330 /// `String::from_utf8_lossy(&self.bytes()?).lines().count()` — a `\n`
331 /// byte is always a `\n` character in UTF-8, and lossy replacement never
332 /// introduces one — but without copying the content out.
333 pub fn line_count(&self) -> usize {
334 fn count(b: &[u8]) -> usize {
335 let nl = bytecount(b);
336 if b.is_empty() || b.ends_with(b"\n") {
337 nl
338 } else {
339 nl + 1
340 }
341 }
342 fn bytecount(b: &[u8]) -> usize {
343 b.iter().filter(|c| **c == b'\n').count()
344 }
345 match &self.content {
346 BlobContent::Resolved(b) => count(b),
347 BlobContent::Lazy(l) => l.force().map(|b| count(&b)).unwrap_or(1),
348 BlobContent::Conflict(sides) => count(&render_conflict(sides)),
349 }
350 }
351 /// the content hash of a lazy blob, if it is one (used to persist an
352 /// unchanged blob without reading its bytes)
353 pub fn lazy_id(&self) -> Option<&str> {
354 match &self.content {
355 BlobContent::Lazy(l) => Some(&l.id),
356 _ => None,
357 }
358 }
361/// Render a conflict with jj-style markers; a side the path is absent on
362/// renders as empty content, as jj materialises it.
363pub fn render_conflict(sides: &[Option<ConflictSide>]) -> Vec<u8> {
364 // sides: [add0, remove0, add1, remove1, ... addN]
365 let mut out = Vec::new();
366 out.extend_from_slice(b"<<<<<<<\n");
367 let mut i = 0;
368 while i < sides.len() {
369 let bytes: &[u8] = sides[i].as_ref().map_or(&[], |s| &s.bytes);
370 if i % 2 == 0 {
371 out.extend_from_slice(b"+++++++\n");
372 out.extend_from_slice(bytes);
373 ensure_newline(&mut out);
374 } else {
375 out.extend_from_slice(b"%%%%%%%\n");
376 out.extend_from_slice(bytes);
377 ensure_newline(&mut out);
378 }
379 i += 1;
380 }
381 out.extend_from_slice(b">>>>>>>\n");
382 out
385fn ensure_newline(v: &mut Vec<u8>) {
386 if !v.is_empty() && !v.ends_with(b"\n") {
387 v.push(b'\n');
388 }
391#[derive(Clone, Copy, PartialEq, Eq, Debug)]
392pub enum PrimKind {
393 Int,
394 Text,
395 Bool,
396 Id,
397 Blob,
400impl PrimKind {
401 pub fn name(&self) -> &'static str {
402 match self {
403 PrimKind::Int => "Int",
404 PrimKind::Text => "Text",
405 PrimKind::Bool => "Bool",
406 PrimKind::Id => "Id",
407 PrimKind::Blob => "Blob",
408 }
409 }
412#[derive(Clone, PartialEq, Eq, Debug)]
413pub enum ShapeKind {
414 Record(BTreeSet<String>),
415 Prim(PrimKind),
418#[derive(Clone, Debug)]
419pub struct ShapeVal {
420 pub name: String,
421 pub kind: ShapeKind,
424impl PartialEq for ShapeVal {
425 fn eq(&self, other: &Self) -> bool {
426 self.kind == other.kind
427 }
430pub type BuiltinFn = fn(&mut crate::eval::Interp, &[Value]) -> Result<Value, Crash>;
432pub enum FunVal {
433 Builtin {
434 name: String,
435 arity: usize,
436 args: Vec<Value>,
437 f: BuiltinFn,
438 /// the name this function is under, its contract as further
439 /// arguments arrive, and how many of `args` it held when it was
440 /// given that name, which are its value's, not the arguments a
441 /// signed definition was given (§5.2)
442 pending: Option<(String, Rc<crate::shape::ContractExpr>, usize)>,
443 },
444 Closure {
445 name: Option<String>, // top-level definition name, if any
446 params: Vec<Pattern>,
447 applied: usize,
448 /// the arguments supplied so far, for rendering (§5.2)
449 applied_args: Vec<Value>,
450 body: Rc<Expr>,
451 env: Env,
452 /// the lambda's source, which it renders as (§5.2)
453 src: crate::ast::Source,
454 /// contract of this function as further arguments arrive
455 pending: Option<(String, Rc<crate::shape::ContractExpr>)>,
456 },
457 /// `f or g` lifted pointwise over functions (§4.6)
458 OrFun(Value, Value),
459 /// a composition `f . g` applied as `f (g x)` (§4.9); `(.)` itself
460 /// builds a builtin node instead (builtins::compose_values)
461 ComposeLazy(Value, Value),
462 /// a label literal %name: applies as `labelled "name"`
463 Labelled(String, Value),
466/// What a function holds that may hold further functions: a closure's
467/// environment and arguments, a builtin's arguments, the operands of an
468/// `or` or a composition, a label's `labelled`. It is only ever dropped.
469#[allow(dead_code)]
470enum Held {
471 Closure(Env, Vec<Value>),
472 Args(Vec<Value>),
473 Two(Value, Value),
474 One(Value),
477/// How many function drops run inside one another before the next one's
478/// contents are put off to the outermost.
479const INLINE_FUN_DROPS: usize = 64;
481struct FunDrops {
482 depth: std::cell::Cell<usize>,
483 put_off: std::cell::RefCell<Vec<Held>>,
486thread_local! {
487 static FUN_DROPS: FunDrops = const {
488 FunDrops {
489 depth: std::cell::Cell::new(0),
490 put_off: std::cell::RefCell::new(Vec::new()),
491 }
492 };
495/// A function is dropped with what it holds, which may be a function holding
496/// a function, and so on: a closure over a closure, a composition of
497/// compositions, a named wrapper around another (named_apply). Dropped the
498/// usual way, such a chain recursed once per link on the native stack, and a
499/// chain a recursion had built a million links long aborted the process
500/// (§4.1). Past a small depth, what a function holds is put off, and the
501/// outermost function drop drops it, so the stack a drop takes is bounded.
502impl Drop for FunVal {
503 fn drop(&mut self) {
504 let held = match self {
505 FunVal::Closure {
506 env, applied_args, ..
507 } => Held::Closure(std::mem::replace(env, Env::empty()), std::mem::take(applied_args)),
508 FunVal::Builtin { args, .. } => Held::Args(std::mem::take(args)),
509 FunVal::OrFun(a, b) | FunVal::ComposeLazy(a, b) => Held::Two(
510 std::mem::replace(a, Value::Bool(false)),
511 std::mem::replace(b, Value::Bool(false)),
512 ),
513 FunVal::Labelled(_, v) => Held::One(std::mem::replace(v, Value::Bool(false))),
514 };
515 // once the thread's locals are gone, `held` simply drops here
516 let _ = FUN_DROPS.try_with(move |d| {
517 let depth = d.depth.get();
518 if depth >= INLINE_FUN_DROPS {
519 d.put_off.borrow_mut().push(held);
520 return;
521 }
522 d.depth.set(depth + 1);
523 drop(held);
524 if depth == 0 {
525 loop {
526 let next = d.put_off.borrow_mut().pop();
527 match next {
528 Some(h) => drop(h),
529 None => break,
530 }
531 }
532 }
533 d.depth.set(depth);
534 });
535 }
538impl Value {
539 pub fn kind_name(&self) -> &'static str {
540 match self {
541 Value::Int(_) => "Int",
542 Value::Text(_) => "Text",
543 Value::Bool(_) => "Bool",
544 Value::List(_) => "list",
545 Value::Record(_) => "record",
546 Value::Fun(_) => "function",
547 Value::Id(_) => "Id",
548 Value::Blob(_) => "Blob",
549 Value::Shape(_) => "Shape",
550 // a thunk stands in for its eventual value (currently a list of
551 // file entries); kind_name is used in error messages
552 Value::Thunk(_) => "list",
553 }
554 }
556 pub fn record(fields: &[(&str, Value)]) -> Value {
557 let mut m = RecordMap::new();
558 for (k, v) in fields {
559 m.insert(k.to_string(), v.clone());
560 }
561 Value::Record(Rc::new(m))
562 }
564 pub fn field(&self, name: &str) -> Result<Value, Crash> {
565 match self {
566 Value::Record(m) => m
567 .get(name)
568 .cloned()
569 .ok_or_else(|| Crash::new(format!("record has no field `{}`", name)))
570 .and_then(|v| v.forced()),
571 _ => Err(Crash::new(format!(
572 "cannot select field `{}` from a {}",
573 name,
574 self.kind_name()
575 ))),
576 }
577 }
579 pub fn field_set(&self) -> Option<BTreeSet<String>> {
580 match self {
581 Value::Record(m) => Some(m.keys().cloned().collect()),
582 _ => None,
583 }
584 }
586 pub fn as_list(&self) -> Result<&[Value], Crash> {
587 match self {
588 Value::List(xs) => Ok(xs.as_slice()),
589 _ => Err(Crash::new(format!("expected a list, got a {}", self.kind_name()))),
590 }
591 }
593 pub fn as_text(&self) -> Result<&str, Crash> {
594 match self {
595 Value::Text(t) => Ok(t),
596 _ => Err(Crash::new(format!("expected Text, got a {}", self.kind_name()))),
597 }
598 }
600 pub fn as_int(&self) -> Result<&BigInt, Crash> {
601 match self {
602 Value::Int(n) => Ok(n),
603 _ => Err(Crash::new(format!("expected Int, got a {}", self.kind_name()))),
604 }
605 }
607 pub fn text(s: impl Into<String>) -> Value {
608 Value::Text(Rc::new(s.into()))
609 }
611 pub fn int(n: i64) -> Value {
612 Value::Int(BigInt::from(n))
613 }
615 pub fn list(xs: Vec<Value>) -> Value {
616 Value::List(ListVal::new(xs))
617 }
619 pub fn bool(b: bool) -> Value {
620 Value::Bool(b)
621 }
624/// Attach a definition name and contract to a function value (§4.13).
625pub fn attach_pending(v: &Value, name: &str, contract: Rc<crate::shape::Contract>) -> Value {
626 let cexpr = Rc::new(crate::shape::ContractExpr::Known { contract, at: 0 });
627 let pending = Some((name.to_string(), cexpr.clone()));
628 match v {
629 Value::Fun(fv) => match fv.as_ref() {
630 FunVal::Closure {
631 params,
632 applied,
633 body,
634 env,
635 src,
636 ..
637 } => Value::Fun(Rc::new(FunVal::Closure {
638 name: Some(name.to_string()),
639 params: params.clone(),
640 applied: *applied,
641 // the definition renders as its name, followed only by the
642 // arguments it is given, not those its value holds: `prev`,
643 // not `prev (parents)` (§5.2)
644 applied_args: Vec::new(),
645 body: body.clone(),
646 env: env.clone(),
647 src: src.clone(),
648 pending,
649 })),
650 FunVal::Builtin {
651 name: bname,
652 arity,
653 args,
654 f,
655 ..
656 } => Value::Fun(Rc::new(FunVal::Builtin {
657 name: bname.clone(),
658 arity: *arity,
659 args: args.clone(),
660 f: *f,
661 // the arguments it holds now are its value's, and those
662 // after them the definition's own: `k3 ((+)) 0` with
663 // `k3 = foldl`, past a signature that ends in a type
664 // variable and so stops counting (§5.2)
665 pending: Some((name.to_string(), cexpr, args.len())),
666 })),
667 // `f or g` and `%name` have nowhere to hold a contract, so the
668 // definition becomes `\x -> v x` under its name, which the
669 // closure machinery checks at every argument the signature lists
670 // and at the result. The check is around the lifted `or` as a
671 // whole (§4.6): a result that violates the signature is a crash,
672 // not a reason to try the other side.
673 FunVal::OrFun(_, _) | FunVal::ComposeLazy(_, _) | FunVal::Labelled(_, _) => {
674 named_apply(v.clone(), Vec::new(), name, cexpr)
675 }
676 },
677 _ => v.clone(),
678 }
681/// `\x -> f x` under a definition's name and contract: it renders as the
682/// name followed by `applied_args` (§5.2), and its further arguments and its
683/// result are checked against the contract (§4.13)
684pub fn named_apply(
685 f: Value,
686 applied_args: Vec<Value>,
687 name: &str,
688 cexpr: Rc<crate::shape::ContractExpr>,
689) -> Value {
690 Value::Fun(Rc::new(FunVal::Closure {
691 name: Some(name.to_string()),
692 params: vec![Pattern::Var("x".to_string())],
693 applied: 0,
694 applied_args,
695 body: NAMED_APPLY_BODY.with(Rc::clone),
696 env: Env::empty().extend(vec![("f".to_string(), f)]),
697 // a named closure renders by its name, not its source (§5.2)
698 src: crate::ast::Source::new(Rc::from(""), 0, 0),
699 pending: Some((name.to_string(), cexpr)),
700 }))
703thread_local! {
704 /// `f x`, the body every named_apply wrapper shares, by which one is
705 /// told from a lambda written in the language
706 static NAMED_APPLY_BODY: Rc<Expr> = {
707 let var = |n: &str| Rc::new(Expr::Var(n.to_string()));
708 Rc::new(Expr::App(var("f"), var("x")))
709 };
712/// The function `v` wraps when it is a named_apply wrapper under `name` and a
713/// contract the same as `cexpr`. Naming that function afresh under them
714/// checks all the wrapper would, so a definition that names the value of its
715/// own recursive call wraps it once, not once per call (§4.13).
716pub fn named_inner(v: &Value, name: &str, cexpr: &crate::shape::ContractExpr) -> Option<Value> {
717 match v {
718 Value::Fun(fv) => match fv.as_ref() {
719 FunVal::Closure {
720 body,
721 env,
722 pending: Some((n, c)),
723 ..
724 } if n == name
725 && c.same_as(cexpr)
726 && NAMED_APPLY_BODY.with(|b| Rc::ptr_eq(b, body)) =>
727 {
728 env.lookup("f")
729 }
730 _ => None,
731 },
732 _ => None,
733 }
736/// A crash (§4.7).
737#[derive(Debug, Clone)]
738pub struct Crash {
739 pub msg: String,
740 /// innermost base definition executing, if any
741 pub def: Option<String>,
744impl Crash {
745 pub fn new(msg: impl Into<String>) -> Crash {
746 Crash {
747 msg: msg.into(),
748 def: None,
749 }
750 }
753// ----------------------------------------------------------------------
754// Environments (persistent, for closures)
755// ----------------------------------------------------------------------
757#[derive(Clone)]
758pub struct Env {
759 frame: Option<Rc<Frame>>,
762pub struct Frame {
763 kind: FrameKind,
764 parent: Env,
767enum FrameKind {
768 Small(Vec<(String, Value)>),
769 Big(HashMap<String, Value>),
770 /// recursive let bindings: the names the block binds, and their values
771 /// in that order, filled incrementally and read through the cell so
772 /// closures capturing the frame see later bindings (§4.1)
773 Rec(Rc<[String]>, Rc<std::cell::RefCell<Vec<Value>>>),
776impl Env {
777 pub fn empty() -> Env {
778 Env { frame: None }
779 }
781 pub fn with_globals(globals: HashMap<String, Value>) -> Env {
782 Env {
783 frame: Some(Rc::new(Frame {
784 kind: FrameKind::Big(globals),
785 parent: Env::empty(),
786 })),
787 }
788 }
790 pub fn extend(&self, bindings: Vec<(String, Value)>) -> Env {
791 Env {
792 frame: Some(Rc::new(Frame {
793 kind: FrameKind::Small(bindings),
794 parent: self.clone(),
795 })),
796 }
797 }
799 /// extend with a recursive frame (for `let` blocks) binding `names`,
800 /// whose values are pushed to the returned cell in the same order
801 pub fn extend_rec(&self, names: Rc<[String]>) -> (Env, Rc<std::cell::RefCell<Vec<Value>>>) {
802 let cell = Rc::new(std::cell::RefCell::new(Vec::with_capacity(names.len())));
803 (
804 Env {
805 frame: Some(Rc::new(Frame {
806 kind: FrameKind::Rec(names, cell.clone()),
807 parent: self.clone(),
808 })),
809 },
810 cell,
811 )
812 }
814 pub fn lookup(&self, name: &str) -> Option<Value> {
815 let mut cur = self.frame.as_ref();
816 while let Some(f) = cur {
817 match &f.kind {
818 FrameKind::Small(bs) => {
819 for (n, v) in bs.iter().rev() {
820 if n == name {
821 return Some(v.clone());
822 }
823 }
824 }
825 FrameKind::Rec(names, cell) => {
826 // the frame binds its names before it holds their values:
827 // one not evaluated yet is unbound here, not a same-named
828 // definition further out, which config.j's binders may
829 // reuse (§4.2)
830 if let Some(i) = names.iter().rposition(|n| n == name) {
831 return cell.borrow().get(i).cloned();
832 }
833 }
834 FrameKind::Big(m) => {
835 if let Some(v) = m.get(name) {
836 return Some(v.clone());
837 }
838 }
839 }
840 cur = f.parent.frame.as_ref();
841 }
842 None
843 }
845 /// True if this environment captures anything beyond the globals frame
846 /// (i.e. the closure was created inside a lambda/let body).
847 pub fn is_closure_capture(&self) -> bool {
848 let mut cur = self.frame.as_ref();
849 let mut small_frames = 0;
850 while let Some(f) = cur {
851 match &f.kind {
852 FrameKind::Small(_) => small_frames += 1,
853 FrameKind::Big(_) | FrameKind::Rec(..) => {}
854 }
855 cur = f.parent.frame.as_ref();
856 }
857 small_frames > 0
858 }
860 pub fn names(&self, out: &mut BTreeSet<String>) {
861 let mut cur = self.frame.as_ref();
862 while let Some(f) = cur {
863 match &f.kind {
864 FrameKind::Small(bs) => {
865 for (n, _) in bs {
866 out.insert(n.clone());
867 }
868 }
869 FrameKind::Rec(names, _) => {
870 for n in names.iter() {
871 out.insert(n.clone());
872 }
873 }
874 FrameKind::Big(m) => {
875 for n in m.keys() {
876 out.insert(n.clone());
877 }
878 }
879 }
880 cur = f.parent.frame.as_ref();
881 }
882 }
885// ----------------------------------------------------------------------
886// structural equality (§4.5); comparing functions is a crash
887// ----------------------------------------------------------------------
889pub fn value_eq(a: &Value, b: &Value) -> Result<bool, Crash> {
890 // force thunks at the boundary so callers never see them
891 if let Value::Thunk(_) = a {
892 return value_eq(&a.forced()?, b);
893 }
894 if let Value::Thunk(_) = b {
895 return value_eq(a, &b.forced()?);
896 }
897 Ok(match (a, b) {
898 (Value::Int(x), Value::Int(y)) => x == y,
899 (Value::Text(x), Value::Text(y)) => x == y,
900 (Value::Bool(x), Value::Bool(y)) => x == y,
901 (Value::Id(x), Value::Id(y)) => x == y,
902 (Value::List(x), Value::List(y)) => {
903 if x.len() != y.len() {
904 return Ok(false);
905 }
906 for (u, v) in x.iter().zip(y.iter()) {
907 if !value_eq(u, v)? {
908 return Ok(false);
909 }
910 }
911 true
912 }
913 (Value::Record(x), Value::Record(y)) => {
914 if x.len() != y.len() {
915 return Ok(false);
916 }
917 for ((k1, v1), (k2, v2)) in x.iter().zip(y.iter()) {
918 if k1 != k2 || !value_eq(v1, v2)? {
919 return Ok(false);
920 }
921 }
922 true
923 }
924 (Value::Blob(x), Value::Blob(y)) => {
925 x.kind == y.kind && blob_content_eq(&x.content, &y.content)?
926 }
927 (Value::Shape(x), Value::Shape(y)) => x == y,
928 (Value::Fun(_), Value::Fun(_)) => {
929 return Err(Crash::new("cannot compare functions for equality"))
930 }
931 _ => false,
932 })
935/// content equality; two lazy blobs compare by content hash, without forcing
936fn blob_content_eq(a: &BlobContent, b: &BlobContent) -> Result<bool, Crash> {
937 Ok(match (a, b) {
938 (BlobContent::Resolved(x), BlobContent::Resolved(y)) => x == y,
939 (BlobContent::Lazy(x), BlobContent::Lazy(y)) => x.id == y.id,
940 (BlobContent::Lazy(x), BlobContent::Resolved(y))
941 | (BlobContent::Resolved(y), BlobContent::Lazy(x)) => x.force()? == *y,
942 (BlobContent::Conflict(x), BlobContent::Conflict(y)) => x == y,
943 _ => false,
944 })
947impl std::fmt::Debug for Value {
948 fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result {
949 // cheap debug rendering without an interpreter
950 match self {
951 Value::Int(n) => write!(f, "Int({})", n),
952 Value::Text(t) => write!(f, "Text({:?})", t),
953 Value::Bool(b) => write!(f, "Bool({})", b),
954 Value::Id(i) => write!(f, "Id(@{})", i),
955 Value::List(xs) => f.debug_list().entries(xs.iter()).finish(),
956 Value::Record(m) => f.debug_map().entries(m.iter()).finish(),
957 Value::Fun(_) => write!(f, "Fun(..)"),
958 Value::Blob(b) => write!(f, "Blob({:?})", b),
959 Value::Shape(s) => write!(f, "Shape({})", s.name),
960 Value::Thunk(t) => write!(f, "{:?}", t),
961 }
962 }