feat(tvix/eval): implement initial compiler::optimiser module r/5602

This optimiser can rewrite some expressions into more efficient forms,
and warn users about those cases.

As a proof-of-concept, only some simple boolean comparisons are
supported for now.

Change-Id: I7df561118cfbad281fc99523e859bc66e7a1adcb
Reviewed-on: https://cl.tvl.fyi/c/depot/+/7766
Tested-by: BuildkiteCI
Reviewed-by: flokli <flokli@flokli.de>

5 files changed, 165 insertions, 0 deletions

diff --git a/tvix/eval/src/compiler/mod.rs b/tvix/eval/src/compiler/mod.rs
index d5afe47d73b2..2f4fc4da64b6 100644
--- a/tvix/eval/src/compiler/mod.rs
+++ b/tvix/eval/src/compiler/mod.rs
@@ -15,6 +15,7 @@
 
 mod bindings;
 mod import;
+mod optimiser;
 mod scope;
 
 use codemap::Span;
@@ -230,6 +231,8 @@ impl Compiler<'_> {
 // Actual code-emitting AST traversal methods.
 impl Compiler<'_> {
     fn compile(&mut self, slot: LocalIdx, expr: ast::Expr) {
+        let expr = optimiser::optimise_expr(self, expr);
+
         match &expr {
             ast::Expr::Literal(literal) => self.compile_literal(literal),
             ast::Expr::Path(path) => self.compile_path(slot, path),
diff --git a/tvix/eval/src/compiler/optimiser.rs b/tvix/eval/src/compiler/optimiser.rs
new file mode 100644
index 000000000000..533b6c540c25
--- /dev/null
+++ b/tvix/eval/src/compiler/optimiser.rs
@@ -0,0 +1,127 @@
+//! Helper functions for extending the compiler with more linter-like
+//! functionality while compiling (i.e. smarter warnings).
+
+use super::*;
+
+use ast::Expr;
+
+/// Optimise the given expression where possible.
+pub(super) fn optimise_expr(c: &mut Compiler, expr: ast::Expr) -> ast::Expr {
+    match expr {
+        Expr::BinOp(_) => optimise_bin_op(c, expr),
+        _ => expr.to_owned(),
+    }
+}
+
+enum LitBool {
+    Expr(Expr),
+    True(Expr),
+    False(Expr),
+}
+
+/// Is this a literal boolean, or something else?
+fn is_lit_bool(expr: ast::Expr) -> LitBool {
+    if let ast::Expr::Ident(ident) = &expr {
+        match ident.ident_token().unwrap().text() {
+            "true" => LitBool::True(expr),
+            "false" => LitBool::False(expr),
+            _ => LitBool::Expr(expr),
+        }
+    } else {
+        LitBool::Expr(expr)
+    }
+}
+
+/// Detect useless binary operations (i.e. useless bool comparisons).
+fn optimise_bin_op(c: &mut Compiler, expr: ast::Expr) -> ast::Expr {
+    use ast::BinOpKind;
+
+    // bail out of this check if the user has poisoned either `true`
+    // or `false` identifiers. Note that they will have received a
+    // separate warning about this for shadowing the global(s).
+    if c.scope().is_poisoned("true") || c.scope().is_poisoned("false") {
+        return expr;
+    }
+
+    if let Expr::BinOp(op) = &expr {
+        let lhs = is_lit_bool(op.lhs().unwrap());
+        let rhs = is_lit_bool(op.rhs().unwrap());
+
+        match (op.operator().unwrap(), lhs, rhs) {
+            // useless `false` arm in `||` expression
+            (BinOpKind::Or, LitBool::False(f), LitBool::Expr(other))
+            | (BinOpKind::Or, LitBool::Expr(other), LitBool::False(f)) => {
+                c.emit_warning(
+                    &f,
+                    WarningKind::UselessBoolOperation(
+                        "this `false` has no effect on the result of the comparison",
+                    ),
+                );
+
+                return other;
+            }
+
+            // useless `true` arm in `&&` expression
+            (BinOpKind::And, LitBool::True(t), LitBool::Expr(other))
+            | (BinOpKind::And, LitBool::Expr(other), LitBool::True(t)) => {
+                c.emit_warning(
+                    &t,
+                    WarningKind::UselessBoolOperation(
+                        "this `true` has no effect on the result of the comparison",
+                    ),
+                );
+
+                return other;
+            }
+
+            // useless `||` expression (one arm is `true`), return
+            // `true` directly (and warn about dead code on the right)
+            (BinOpKind::Or, LitBool::True(t), LitBool::Expr(other)) => {
+                c.emit_warning(
+                    op,
+                    WarningKind::UselessBoolOperation("this expression is always true"),
+                );
+
+                // TODO: still compile other to get errors/warnings from there, but don't emit
+                c.emit_warning(&other, WarningKind::DeadCode);
+
+                return t;
+            }
+
+            (BinOpKind::Or, _, LitBool::True(t)) | (BinOpKind::Or, LitBool::True(t), _) => {
+                c.emit_warning(
+                    op,
+                    WarningKind::UselessBoolOperation("this expression is always true"),
+                );
+
+                return t;
+            }
+
+            // useless `&&` expression (one arm is `false), same as above
+            (BinOpKind::And, LitBool::False(f), LitBool::Expr(other)) => {
+                c.emit_warning(
+                    op,
+                    WarningKind::UselessBoolOperation("this expression is always false"),
+                );
+
+                // TODO: still compile other to get errors/warnings from there, but don't emit
+                c.emit_warning(&other, WarningKind::DeadCode);
+
+                return f;
+            }
+
+            (BinOpKind::And, _, LitBool::False(f)) | (BinOpKind::Or, LitBool::False(f), _) => {
+                c.emit_warning(
+                    op,
+                    WarningKind::UselessBoolOperation("this expression is always false"),
+                );
+
+                return f;
+            }
+
+            _ => { /* nothing to optimise */ }
+        }
+    }
+
+    expr
+}
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.exp b/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.exp
new file mode 100644
index 000000000000..9d9185fcd155
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.exp
@@ -0,0 +1 @@
+[ true true false false true true false false ]
diff --git a/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.nix b/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.nix
new file mode 100644
index 000000000000..650d7f028df2
--- /dev/null
+++ b/tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.nix
@@ -0,0 +1,21 @@
+let
+  makeTrue = _: true;
+  makeFalse = _: false;
+in
+[
+  # useless `false`
+  (false || makeTrue null) # true
+  (makeTrue null || false) # true
+
+  # useless `true`
+  (true && makeFalse null) # false
+  (makeFalse null && true) # false
+
+  # useless `||`
+  (true || makeFalse null) # true
+  (makeFalse null || true) # true
+
+  # useless `&&`
+  (false && makeTrue null) # false
+  (makeTrue null && false) # false
+]
diff --git a/tvix/eval/src/warnings.rs b/tvix/eval/src/warnings.rs
index eb821b2b8324..9fb454e8147c 100644
--- a/tvix/eval/src/warnings.rs
+++ b/tvix/eval/src/warnings.rs
@@ -13,6 +13,8 @@ pub enum WarningKind {
     ShadowedGlobal(&'static str),
     DeprecatedLegacyLet,
     InvalidNixPath(String),
+    UselessBoolOperation(&'static str),
+    DeadCode,
 
     /// Tvix internal warning for features triggered by users that are
     /// not actually implemented yet, but do not cause runtime failures.
@@ -85,6 +87,14 @@ impl EvalWarning {
                 format!("invalid NIX_PATH resulted in a parse error: {}", err)
             }
 
+            WarningKind::UselessBoolOperation(msg) => {
+                format!("useless operation on boolean: {}", msg)
+            }
+
+            WarningKind::DeadCode => {
+                format!("this code will never be executed")
+            }
+
             WarningKind::NotImplemented(what) => {
                 format!("feature not yet implemented in tvix: {}", what)
             }
@@ -101,6 +111,9 @@ impl EvalWarning {
             WarningKind::ShadowedGlobal(_) => "W004",
             WarningKind::DeprecatedLegacyLet => "W005",
             WarningKind::InvalidNixPath(_) => "W006",
+            WarningKind::UselessBoolOperation(_) => "W007",
+            WarningKind::DeadCode => "W008",
+
             WarningKind::NotImplemented(_) => "W999",
         }
     }