feat(tvix/eval): builtins.import without RefCell r/5213

CL/6867 added support for builtins.import, which required a cyclic
reference import->globals->builtins->import.  This was implemented
using a RefCell, which makes it possible to mutate the builtins
during evaluation.  The commit message for CL/6867 expressed a
desire to eliminate this possibility:

  This opens up a potentially dangerous footgun in which we could
  mutate the builtins at runtime leading to different compiler
  invocations seeing different builtins, so it'd be nice to have
  some kind of "finalised" status for them or some such, but I'm not
  sure how to represent that atm.

This CL replaces the RefCell with Rc::new_cyclic(), making the
globals/builtins immutable once again.  At VM runtime (once opcodes
start executing) everything is the same as before this CL, except
that the Rc<RefCell<>> introduced by CL/6867 is turned into an
rc::Weak<>.

The function passed to Rc::new_cyclic works very similarly to
overlays in nixpkgs: a function takes its own result as an argument.
However instead of laziness "breaking the cycle", Rust's
Rc::new_cyclic() instead uses an rc::Weak.  This is done to prevent
memory leaks rather than divergence.

This CL also resolves the following TODO from CL/6867:

  // TODO: encapsulate this import weirdness in builtins

The main disadvantage of this CL is the fact that the VM now must
ensure that it holds a strong reference to the globals while a
program is executing; failure to do so will cause a panic when the
weak reference in the builtins is upgrade()d.

In theory it should be possible to create strong reference cycles
the same way Rc::new_cyclic() creates weak cycles, but these cycles
would cause a permanent memory leak -- without either an rc::Weak or
RefCell there is no way to break the cycle.  At some point we will
have to implement some form of cycle collection; whatever library we
choose for that purpose is likely to provide an "immutable strong
reference cycle" primitive similar to Rc::new_cyclic(), and we
should be able to simply drop it in.

Signed-off-by: Adam Joseph <adam@westernsemico.com>
Change-Id: I34bb5821628eb97e426bdb880b02e2097402adb7
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7097
Tested-by: BuildkiteCI
Reviewed-by: tazjin <tazjin@tvl.su>

1 files changed, 24 insertions, 14 deletions

diff --git a/tvix/eval/src/builtins/impure.rs b/tvix/eval/src/builtins/impure.rs
index 5edd81999a7c..8433c04c419d 100644
--- a/tvix/eval/src/builtins/impure.rs
+++ b/tvix/eval/src/builtins/impure.rs
@@ -1,17 +1,17 @@
 use std::{
-    cell::RefCell,
-    collections::{BTreeMap, HashMap},
+    collections::BTreeMap,
     env,
     fs::File,
     io::{self, Read},
-    rc::Rc,
+    rc::{Rc, Weak},
     time::{SystemTime, UNIX_EPOCH},
 };
 
 use crate::{
+    compiler::GlobalsMap,
     errors::ErrorKind,
     observer::NoOpObserver,
-    value::{Builtin, NixAttrs, NixString, Thunk},
+    value::{Builtin, NixAttrs, Thunk},
     vm::VM,
     SourceCode, Value,
 };
@@ -69,10 +69,10 @@ fn impure_builtins() -> Vec<Builtin> {
 
 /// Return all impure builtins, that is all builtins which may perform I/O
 /// outside of the VM and so cannot be used in all contexts (e.g. WASM).
-pub(super) fn builtins() -> BTreeMap<NixString, Value> {
-    let mut map: BTreeMap<NixString, Value> = impure_builtins()
+pub(super) fn builtins() -> BTreeMap<&'static str, Value> {
+    let mut map: BTreeMap<&'static str, Value> = impure_builtins()
         .into_iter()
-        .map(|b| (b.name().into(), Value::Builtin(b)))
+        .map(|b| (b.name(), Value::Builtin(b)))
         .collect();
 
     // currentTime pins the time at which evaluation was started
@@ -84,7 +84,7 @@ pub(super) fn builtins() -> BTreeMap<NixString, Value> {
             Err(err) => -(err.duration().as_secs() as i64),
         };
 
-        map.insert(NixString::from("currentTime"), Value::Integer(seconds));
+        map.insert("currentTime", Value::Integer(seconds));
     }
 
     map
@@ -94,10 +94,13 @@ pub(super) fn builtins() -> BTreeMap<NixString, Value> {
 /// it needs to capture the [crate::SourceCode] structure to correctly track
 /// source code locations while invoking a compiler.
 // TODO: need to be able to pass through a CompilationObserver, too.
-pub fn builtins_import(
-    globals: Rc<RefCell<HashMap<&'static str, Value>>>,
-    source: SourceCode,
-) -> Builtin {
+pub fn builtins_import(globals: &Weak<GlobalsMap>, source: SourceCode) -> Builtin {
+    // This (very cheap, once-per-compiler-startup) clone exists
+    // solely in order to keep the borrow checker happy.  It
+    // resolves the tension between the requirements of
+    // Rc::new_cyclic() and Builtin::new()
+    let globals = globals.clone();
+
     Builtin::new(
         "import",
         &[true],
@@ -126,11 +129,18 @@ pub fn builtins_import(
                 });
             }
 
-            let result = crate::compile(
+            let result = crate::compiler::compile(
                 &parsed.tree().expr().unwrap(),
                 Some(path.clone()),
                 file,
-                globals.clone(),
+                // The VM must ensure that a strong reference to the
+                // globals outlives any self-references (which are
+                // weak) embedded within the globals.  If the
+                // expect() below panics, it means that did not
+                // happen.
+                globals
+                    .upgrade()
+                    .expect("globals dropped while still in use"),
                 &mut NoOpObserver::default(),
             )
             .map_err(|err| ErrorKind::ImportCompilerError {