Repository: tweag/nickel
Pull request #1978 (2024-06-26 18:05:00)

Allow some function equality comparison
Relax the initial restriction on comparing functions, introduced in #975, which is that comparing a function to anything else errors out. In practice comparing a function to a value of some other type isn't a problem, and can be useful to allow patterns like `fun x => if x != null then ... else ...` without having first to defensively check if `x` is a function, because that would fail at runtime. One can think for example of quick contracts such as `let IsZero = from_predicate ((==) 0)`, which currently fails with a dynamic type error if we try to do `(fun x => x) | IsZero`. We'd need to do something like `from_predicate (fun x => !(std.is_function x) && x == 0)`, which is annoying.

Instead, we only forbid comparison between two function-like values (functions, match expressions and custom contracts) and between two opaque foreign values. Comparing a function-like value to a number of a string is fine and just returns false.

The initial motivation for restricting function comparison is that it's never something that is meaningful to do, so it's most probably an error, and that it breaks reflexivity of `==`, because `f != f` when `f` is a function. Arguably, the relaxed restriction proposed in this PR still fits the bill.

For context, this came up in #1975, where custom contracts is internally a pair of function `(immediate, delayed)`, each of which can be `null`, but then we can't do control flow such as `if immediate != null then ...`. While the `%typeof%` work-around does work, it doesn't feel right.


Patch:
diff --git a/.github/workflows/update-flake-lock.yml b/.github/workflows/update-flake-lock.yml
index 3729890b..59b89d59 100644
--- a/.github/workflows/update-flake-lock.yml
+++ b/.github/workflows/update-flake-lock.yml
@@ -16,7 +16,7 @@ jobs:
           extra_nix_config: |
             access-tokens = github.com=${{ secrets.GITHUB_TOKEN }}
       - name: Update flake.lock
-        uses: DeterminateSystems/update-flake-lock@v22
+        uses: DeterminateSystems/update-flake-lock@v23
         with:
           # Providing a secret token is necessary for the PRs to run CI
           # See https://github.com/DeterminateSystems/update-flake-lock#with-a-personal-authentication-token
diff --git a/core/src/error/mod.rs b/core/src/error/mod.rs
index 4b7dc8c0..17ec9a57 100644
--- a/core/src/error/mod.rs
+++ b/core/src/error/mod.rs
@@ -145,8 +145,12 @@ pub enum EvalError {
         label: label::Label,
         call_stack: CallStack,
     },
-    /// A non-equatable term was compared for equality.
-    EqError { eq_pos: TermPos, term: RichTerm },
+    /// Two non-equatable terms of the same type (e.g. functions) were compared for equality.
+    IncomparableValues {
+        eq_pos: TermPos,
+        left: RichTerm,
+        right: RichTerm,
+    },
     /// A value didn't match any branch of a `match` expression at runtime. This is a specialized
     /// version of [Self::NonExhaustiveMatch] when all branches are enum patterns. In this case,
     /// the error message is more informative than the generic one.
@@ -1365,28 +1369,42 @@ impl IntoDiagnostics<FileId> for EvalError {
                     .with_message(format!("{format} parse error: {msg}"))
                     .with_labels(labels)]
             }
-            EvalError::EqError { eq_pos, term: t } => {
-                let label = format!(
-                    "an argument has type {}, which cannot be compared for equality",
-                    t.term
+            EvalError::IncomparableValues {
+                eq_pos,
+                left,
+                right,
+            } => {
+                let mut labels = Vec::new();
+
+                if let Some(span) = eq_pos.as_opt_ref() {
+                    labels.push(primary(span).with_message("in this equality comparison"));
+                }
+
+                // Push the label for the right or left argument and return the type of said
+                // argument.
+                let mut push_label = |prefix: &str, term: &RichTerm| -> String {
+                    let type_of = term
+                        .term
                         .type_of()
-                        .unwrap_or_else(|| String::from("<unevaluated>")),
-                );
+                        .unwrap_or_else(|| String::from("<unevaluated>"));
 
-                let labels = match eq_pos {
-                    TermPos::Original(pos) | TermPos::Inherited(pos) if eq_pos != t.pos => {
-                        vec![
-                            primary(&pos).with_message(label),
-                            secondary_term(&t, files)
-                                .with_message("problematic argument evaluated to this"),
-                        ]
-                    }
-                    _ => vec![primary_term(&t, files).with_message(label)],
+                    labels.push(
+                        secondary_term(term, files)
+                            .with_message(format!("{prefix} argument has type {type_of}")),
+                    );
+
+                    type_of
                 };
 
+                let left_type = push_label("left", &left);
+                let right_type = push_label("right", &right);
+
                 vec![Diagnostic::error()
                     .with_message("cannot compare values for equality")
-                    .with_labels(labels)]
+                    .with_labels(labels)
+                    .with_notes(vec![format!(
+                        "A {left_type} can't be meaningfully compared with a {right_type}"
+                    )])]
             }
             EvalError::NonExhaustiveEnumMatch {
                 expected,
diff --git a/core/src/eval/operation.rs b/core/src/eval/operation.rs
index ae787df5..84d8c46b 100644
--- a/core/src/eval/operation.rs
+++ b/core/src/eval/operation.rs
@@ -3325,7 +3325,25 @@ impl RecPriority {
 /// # Return
 ///
 /// If the comparison is successful, returns a bool indicating whether the values were equal,
-/// otherwise returns an [`EvalError`] indicating that the values cannot be compared.
+/// otherwise returns an [`EvalError`] indicating that the values cannot be compared (typically two
+/// functions).
+///
+/// # Uncomparable values
+///
+/// Comparing two functions is undecidable. Even in simple cases, it's not trivial to handle an
+/// approximation (functions might capture free variables, you'd need to take eta-conversion into
+/// account to equate e.g. `fun x => x` and `fun y => y`, etc.).
+///
+/// Thus, by default, comparing a function to something else always returns `false`. However, this
+/// breaks the reflexivity property of equality, which users might rightfully rely on, because `fun
+/// x => x` isn't equal to itself. Also, comparing two functions is probably never intentional nor
+/// meaningful: thus we error out when trying to compare two functions. We still allow comparing
+/// functions to something else, because it's useful to have tests like `if value == 1` or `if
+/// value == null` typically in contracts without having to defensively check that `value` is a
+/// function.
+///
+/// The same reasoning applies to foreign values (which we don't want to compare for security
+/// reasons, at least right now, not because we can't).
 fn eq<C: Cache>(
     cache: &mut C,
     c1: Closure,
@@ -3531,22 +3549,18 @@ fn eq<C: Cache>(
                 }
             }
         }
-        (Term::Fun(i, rt), _) => Err(EvalError::EqError {
-            eq_pos: pos_op,
-            term: RichTerm::new(Term::Fun(i, rt), pos1),
-        }),
-        (_, Term::Fun(i, rt)) => Err(EvalError::EqError {
-            eq_pos: pos_op,
-            term: RichTerm::new(Term::Fun(i, rt), pos2),
-        }),
-        (Term::ForeignId(v), _) => Err(EvalError::EqError {
-            eq_pos: pos_op,
-            term: RichTerm::new(Term::ForeignId(v), pos1),
-        }),
-        (_, Term::ForeignId(v)) => Err(EvalError::EqError {
-            eq_pos: pos_op,
-            term: RichTerm::new(Term::ForeignId(v), pos2),
-        }),
+        // Function-like terms and foreign id can't be compared together.
+        (
+            t1 @ (Term::Fun(..) | Term::Match(_) | Term::CustomContract(_)),
+            t2 @ (Term::Fun(..) | Term::Match(_) | Term::CustomContract(_)),
+        )
+        | (t1 @ Term::ForeignId(_), t2 @ Term::ForeignId(_)) => {
+            Err(EvalError::IncomparableValues {
+                eq_pos: pos_op,
+                left: RichTerm::new(t1, pos1),
+                right: RichTerm::new(t2, pos2),
+            })
+        }
         (_, _) => Ok(EqResult::Bool(false)),
     }
 }


Test patch:
diff --git a/core/src/eval/tests.rs b/core/src/eval/tests.rs
index 6af36c07..5ebfd80d 100644
--- a/core/src/eval/tests.rs
+++ b/core/src/eval/tests.rs
@@ -376,7 +376,10 @@ fn foreign_id() {
         RichTerm::from(Term::ForeignId(43)),
         RichTerm::from(Term::ForeignId(42)),
     );
-    assert_matches!(eval_no_import(t_eq), Err(EvalError::EqError { .. }));
+    assert_matches!(
+        eval_no_import(t_eq),
+        Err(EvalError::IncomparableValues { .. })
+    );
 
     // Opaque values cannot be merged (even if they're equal, since they can't get compared for equality).
     let t_merge = mk_term::op2(
diff --git a/core/tests/integration/inputs/contracts/equating_fn_match.ncl b/core/tests/integration/inputs/contracts/equating_fn_match.ncl
new file mode 100644
index 00000000..c456818b
--- /dev/null
+++ b/core/tests/integration/inputs/contracts/equating_fn_match.ncl
@@ -0,0 +1,7 @@
+# test.type = 'error'
+#
+# [test.metadata]
+# error = 'EvalError::IncomparableValues'
+let g = fun x => x + 1 in
+let h = match { 0 => 0 } in
+g == h
diff --git a/core/tests/integration/inputs/contracts/equating_fns_lhs.ncl b/core/tests/integration/inputs/contracts/equating_fns_lhs.ncl
deleted file mode 100644
index d7967c89..00000000
--- a/core/tests/integration/inputs/contracts/equating_fns_lhs.ncl
+++ /dev/null
@@ -1,6 +0,0 @@
-# test.type = 'error'
-#
-# [test.metadata]
-# error = 'EvalError::EqError'
-let f = fun x => x in
-f == 1
\ No newline at end of file
diff --git a/core/tests/integration/inputs/contracts/equating_fns_rhs.ncl b/core/tests/integration/inputs/contracts/equating_functions.ncl
similarity index 58%
rename from core/tests/integration/inputs/contracts/equating_fns_rhs.ncl
rename to core/tests/integration/inputs/contracts/equating_functions.ncl
index b49868b3..62d7f872 100644
--- a/core/tests/integration/inputs/contracts/equating_fns_rhs.ncl
+++ b/core/tests/integration/inputs/contracts/equating_functions.ncl
@@ -1,6 +1,6 @@
 # test.type = 'error'
 #
 # [test.metadata]
-# error = 'EvalError::EqError'
+# error = 'EvalError::IncomparableValues'
 let g = fun x => x + 1 in
-"a" == g
\ No newline at end of file
+g == g
diff --git a/core/tests/integration/inputs/core/eq.ncl b/core/tests/integration/inputs/core/eq.ncl
index f721373c..bc091d2d 100644
--- a/core/tests/integration/inputs/core/eq.ncl
+++ b/core/tests/integration/inputs/core/eq.ncl
@@ -83,5 +83,10 @@
   'Left 1 != 'Left 2,
   'Left 2 != 'Right 2,
   'Up [1,2,3] == 'Up [0+1,1+1,2+1],
+
+  # Functions can be compared to non-functions
+
+  (fun x => x) != 1,
+  ((+) 1) != null,
 ]
 |> std.test.assert_all
diff --git a/core/tests/integration/main.rs b/core/tests/integration/main.rs
index 692fa7dd..4764f4cb 100644
--- a/core/tests/integration/main.rs
+++ b/core/tests/integration/main.rs
@@ -145,8 +145,8 @@ enum Expectation {
 #[serde(tag = "error", content = "expectation")]
 enum ErrorExpectation {
     // TODO: can we somehow unify this with the `Display` impl below?
-    #[serde(rename = "EvalError::EqError")]
-    EvalEqError,
+    #[serde(rename = "EvalError::IncomparableValues")]
+    EvalIncomparableValues,
     #[serde(rename = "EvalError::Other")]
     EvalOther,
     #[serde(rename = "EvalError::UnaryPrimopTypeError")]
@@ -230,7 +230,7 @@ impl PartialEq<Error> for ErrorExpectation {
                 Error::EvalError(EvalError::IllegalPolymorphicTailAccess { .. }),
             )
             | (EvalTypeError, Error::EvalError(EvalError::TypeError(..)))
-            | (EvalEqError, Error::EvalError(EvalError::EqError { .. }))
+            | (EvalIncomparableValues, Error::EvalError(EvalError::IncomparableValues { .. }))
             | (EvalNAryPrimopTypeError, Error::EvalError(EvalError::NAryPrimopTypeError { .. }))
             | (
                 EvalUnaryPrimopTypeError,
@@ -393,7 +393,7 @@ impl std::fmt::Display for ErrorExpectation {
             ImportIoError => "ImportError::IoError".to_owned(),
             EvalBlameError => "EvalError::BlameError".to_owned(),
             EvalTypeError => "EvalError::TypeError".to_owned(),
-            EvalEqError => "EvalError::EqError".to_owned(),
+            EvalIncomparableValues => "EvalError::IncomparableValues".to_owned(),
             EvalOther => "EvalError::Other".to_owned(),
             EvalMergeIncompatibleArgs => "EvalError::MergeIncompatibleArgs".to_owned(),
             EvalNAryPrimopTypeError => "EvalError::NAryPrimopTypeError".to_owned(),