Repository: tweag/nickel
Pull request #587 (2022-01-20 15:38:38)

Fix recursive overriding when merging records with intersecting fields
Fix both #579 and #583. When introducing recursive overriding, what we did when merging was to revert the thunks of the two records being merged, build a new recursive record `RecRecord` with the result of the merging, and let `eval` compute the fixpoint of this record at the next tick. 

To compute the fixpoint, `eval` builds the so-called recursive environment with the content of each field, and then go through each field again in order to extend their environment with this recursive environment. For this to work, we were careful to maintain the invariant that the content of each field of a recursive record was a closure (stored as a variable) whose content was _immediately_ the original expression, without any additional indirection.

This works as long as we are not actually recursively merging fields: that is, when the fields of the two operands of `&` are disjoints like in `{foo = 1} & {bar = 2}`, or when the common fields have different priorities `{foo | default = 1, bar = foo} & {foo = 2}`. There, each field of the end record is directly taken from one of the operand.

However, this isn't so true anymore when we are actually recursively merging fields, as in `{foo | default = 1, m={baz=foo}} & {foo = 2, m={bar=foo}}`. Here, `merge` will closurize the `m` coming from both operands (let's call the result `%m1` and `%m2`), and set `m = %m1 & %m2` in the final result. This breaks the invariant, as `%m1 & %m2` is not an unevaluated expression coming from a recursive record anymore. `eval` would then patch `m` with the recursive environment. Alas, with no effect: `m` doesn't use any free variable from the recursive environment. What we need is to actually patch the environment of `%m1` and `%m2`, not `m`.

In this PR, we:
- extract the record fixpoint computation code from `eval` to a submodule, to avoid duplicating the logic in `eval` and `merge`
- in `merge`, we keep a list of `Rc`s to the fields of both operands _before_ we merge them. We then build the final record, build the final recursive environment, and can eventually patch the environment of the original fields as wanted.


Patch:
diff --git a/src/eval/fixpoint.rs b/src/eval/fixpoint.rs
new file mode 100644
index 00000000..6231bd97
--- /dev/null
+++ b/src/eval/fixpoint.rs
@@ -0,0 +1,51 @@
+//! Compute the fixpoint of a recursive record.
+use super::*;
+
+/// Build a recursive environment from record bindings. For each field, `rec_env` either extracts
+/// the corresponding thunk from the environment in the general case, or create a closure on the
+/// fly if the field is a constant. The resulting environment is to be passed to the
+/// [`patch_field`] function.
+pub fn rec_env<'a, I: Iterator<Item = (&'a Ident, &'a RichTerm)>>(
+    bindings: I,
+    env: &Environment,
+) -> Result<Vec<(Ident, Thunk)>, EvalError> {
+    bindings
+        .map(|(id, rt)| match rt.as_ref() {
+            Term::Var(ref var_id) => {
+                let thunk = env
+                    .get(var_id)
+                    .ok_or_else(|| EvalError::UnboundIdentifier(var_id.clone(), rt.pos))?;
+                Ok((id.clone(), thunk))
+            }
+            _ => {
+                // If we are in this branch, `rt` must be a constant after the share normal form
+                // transformation, hence it should not need an environment, which is why it is
+                // dropped.
+                let closure = Closure {
+                    body: rt.clone(),
+                    env: Environment::new(),
+                };
+                Ok((id.clone(), Thunk::new(closure, IdentKind::Let)))
+            }
+        })
+        .collect()
+}
+
+/// Update the environment of the content of a recursive record field by extending it with a
+/// recursive environment.
+pub fn patch_field(
+    rt: &RichTerm,
+    rec_env: &Vec<(Ident, Thunk)>,
+    env: &Environment,
+) -> Result<(), EvalError> {
+    if let Term::Var(var_id) = &*rt.term {
+        let mut thunk = env
+            .get(var_id)
+            .ok_or_else(|| EvalError::UnboundIdentifier(var_id.clone(), rt.pos))?;
+        thunk.borrow_mut().env.extend(rec_env.iter().cloned());
+    }
+    // Thanks to the share normal form transformation, the content is either a constant or a
+    // variable. In the constant case, the environment is irrelevant and we don't have to do
+    // anything in the `else` case.
+    Ok(())
+}
diff --git a/src/eval/merge.rs b/src/eval/merge.rs
index 231265e9..5a7b591d 100644
--- a/src/eval/merge.rs
+++ b/src/eval/merge.rs
@@ -51,8 +51,8 @@
 //! evaluates to the simple value
 //! - *Contract check*: merging a `Contract` or a `ContractDefault` with a simple value `t`
 //! evaluates to a contract check, that is an `Assume(..., t)`
+use super::*;
 use crate::error::EvalError;
-use crate::eval::{CallStack, Closure, Environment};
 use crate::label::Label;
 use crate::position::TermPos;
 use crate::term::{
@@ -329,8 +329,18 @@ pub fn merge(
              * the same trick as in the evaluation of the operator DynExtend, and replace each such
              * term by a variable bound to an appropriate closure in the environment
              */
+            // Merging recursive record is the one operation that may override recursive fields. To
+            // have the recursive fields depend on the updated values, we need to revert the thunks
+            // first.
             rev_thunks(m1.values_mut(), &mut env1);
             rev_thunks(m2.values_mut(), &mut env2);
+
+            // We save the original fields before they are potentially merged in order to patch
+            // their environment in the final record (cf `fixpoint::patch_fields`). Note that we
+            // are only cloning shared terms (`Rc`s) here.
+            let m1_values: Vec<_> = m1.values().cloned().collect();
+            let m2_values: Vec<_> = m2.values().cloned().collect();
+
             let (left, center, right) = hashmap::split(m1, m2);
 
             match mode {
@@ -362,9 +372,17 @@ pub fn merge(
                 );
             }
 
+            let rec_env = fixpoint::rec_env(m.iter(), &env)?;
+            m1_values
+                .iter()
+                .try_for_each(|rt| fixpoint::patch_field(rt, &rec_env, &env1))?;
+            m2_values
+                .iter()
+                .try_for_each(|rt| fixpoint::patch_field(rt, &rec_env, &env2))?;
+
             Ok(Closure {
                 body: RichTerm::new(
-                    Term::RecRecord(m, Vec::new(), RecordAttrs::merge(attrs1, attrs2)),
+                    Term::Record(m, RecordAttrs::merge(attrs1, attrs2)),
                     pos_op.into_inherited(),
                 ),
                 env,
diff --git a/src/eval/mod.rs b/src/eval/mod.rs
index cdc4cde5..98792482 100644
--- a/src/eval/mod.rs
+++ b/src/eval/mod.rs
@@ -101,6 +101,7 @@ use crate::{
 };
 
 pub mod callstack;
+pub mod fixpoint;
 pub mod lazy;
 pub mod merge;
 pub mod operation;
@@ -498,63 +499,20 @@ where
                 }
             }
             Term::RecRecord(ts, dyn_fields, attrs) => {
-                // Thanks to the share normal form transformation, the content is either a constant or a
-                // variable.
-                let rec_env = ts.iter().try_fold::<_, _, Result<Environment, EvalError>>(
-                    Environment::new(),
-                    |mut rec_env, (id, rt)| match rt.as_ref() {
-                        Term::Var(ref var_id) => {
-                            let thunk = env.get(var_id).ok_or_else(|| {
-                                EvalError::UnboundIdentifier(var_id.clone(), rt.pos)
-                            })?;
-                            rec_env.insert(id.clone(), thunk);
-                            Ok(rec_env)
-                        }
-                        _ => {
-                            // If we are in this branch, the term must be a constant after the
-                            // share normal form transformation, hence it should not need an
-                            // environment, which is why it is dropped.
-                            let closure = Closure {
-                                body: rt.clone(),
-                                env: Environment::new(),
-                            };
-                            rec_env.insert(id.clone(), Thunk::new(closure, IdentKind::Let));
-                            Ok(rec_env)
-                        }
-                    },
-                )?;
-
-                let new_ts = ts.into_iter().map(|(id, rt)| {
-                    let pos = rt.pos;
-                    match &*rt.term {
-                        Term::Var(var_id) => {
-                            // We already checked for unbound identifier in the previous fold,
-                            // so function should always succeed
-                            let mut thunk = env.get(var_id).unwrap();
-                            thunk.borrow_mut().env.extend(
-                                rec_env
-                                    .iter_elems()
-                                    .map(|(id, thunk)| (id.clone(), thunk.clone())),
-                            );
-                            (
-                                id.clone(),
-                                RichTerm {
-                                    term: SharedTerm::new(Term::Var(var_id.clone())),
-                                    pos,
-                                },
-                            )
-                        }
-                        _ => (id.clone(), rt.clone()),
-                    }
-                });
+                let rec_env = fixpoint::rec_env(ts.iter(), &env)?;
+
+                ts.iter()
+                    .try_for_each(|(_, rt)| fixpoint::patch_field(rt, &rec_env, &env))?;
 
-                let static_part = RichTerm::new(Term::Record(new_ts.collect(), attrs.clone()), pos);
+                //TODO: We should probably avoid cloning the `ts` hashmap, using `match_sharedterm`
+                //instead of `match` in the main eval loop, if possible
+                let static_part = RichTerm::new(Term::Record(ts.clone(), attrs.clone()), pos);
 
                 // Transform the static part `{stat1 = val1, ..., statn = valn}` and the dynamic
                 // part `{exp1 = dyn_val1, ..., expm = dyn_valm}` to a sequence of extensions
                 // `{stat1 = val1, ..., statn = valn} $[ exp1 = dyn_val1] ... $[ expn = dyn_valn ]`
-                // The `dyn_val` are given access to the recursive environment, but not the dynamic
-                // field names.
+                // The `dyn_val` are given access to the recursive environment, but the recursive
+                // environment only contains the static fields, and not the dynamic fields.
                 let extended = dyn_fields
                     .into_iter()
                     .try_fold::<_, _, Result<RichTerm, EvalError>>(
@@ -562,29 +520,15 @@ where
                         |acc, (id_t, t)| {
                             let id_t = id_t.clone();
                             let pos = t.pos;
-                            match &*t.term {
-                                Term::Var(var_id) => {
-                                    let mut thunk = env.get(var_id).ok_or_else(|| {
-                                        EvalError::UnboundIdentifier(var_id.clone(), pos)
-                                    })?;
-
-                                    thunk.borrow_mut().env.extend(
-                                        rec_env
-                                            .iter_elems()
-                                            .map(|(id, thunk)| (id.clone(), thunk.clone())),
-                                    );
-                                    Ok(Term::App(
-                                        mk_term::op2(BinaryOp::DynExtend(), id_t, acc),
-                                        mk_term::var(var_id.clone()).with_pos(pos),
-                                    )
-                                    .into())
-                                }
-                                _ => Ok(Term::App(
+
+                            fixpoint::patch_field(t, &rec_env, &env)?;
+                            Ok(RichTerm::new(
+                                Term::App(
                                     mk_term::op2(BinaryOp::DynExtend(), id_t, acc),
                                     t.clone(),
-                                )
-                                .into()),
-                            }
+                                ),
+                                pos.into_inherited(),
+                            ))
                         },
                     )?;
 


Test patch:
diff --git a/tests/pass/records.ncl b/tests/pass/records.ncl
index d43da72b..f6477d46 100644
--- a/tests/pass/records.ncl
+++ b/tests/pass/records.ncl
@@ -79,19 +79,34 @@ let Assert = fun l x => x || %blame% l in
         else g x,
       g = fun y => f (y + (-1))
     }.f 10 in
-    with_res "done" == "done",
+  with_res "done" == "done",
 
-    // piecewise signatures
-    {
-        foo : Num,
-        bar = 3,
-        foo = 5
-    }.foo == 5,
-    {
-        foo : Num,
-        foo = 1,
-        bar : Num = foo,
-    }.bar == 1,
-    let {foo : Num} = {foo = 1} in foo == 1,
+  // piecewise signatures
+  {
+      foo : Num,
+      bar = 3,
+      foo = 5
+  }.foo == 5,
+  {
+      foo : Num,
+      foo = 1,
+      bar : Num = foo,
+  }.bar == 1,
+  let {foo : Num} = {foo = 1} in foo == 1,
+
+  // recursive overriding with common fields
+  // regression tests for [#579](https://github.com/tweag/nickel/issues/579)
+  // and [#583](https://github.com/tweag/nickel/issues/583)
+  ({foo.bar = foo.baz, foo.baz | default = 2} & {foo.baz = 1}).foo.bar == 1,
+  let Name = fun b label name => if b then "hijack" else contracts.blame label in
+  let Config = {
+      b | Bool,
+      name | #(Name b),
+  } in
+  let data | #Config = {
+      b = true,
+      name = "name",
+  } in
+  data.name == "hijack",
 ]
 |> lists.foldl (fun x y => (x | #Assert) && y) true