From 6a8541e35a76b1d0d100c505d395d0e0418377c7 Mon Sep 17 00:00:00 2001 From: Vincent Ambo Date: Thu, 5 Jan 2023 15:11:28 +0300 Subject: feat(tvix/eval): implement initial compiler::optimiser module 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 --- tvix/eval/src/compiler/mod.rs | 3 + tvix/eval/src/compiler/optimiser.rs | 127 +++++++++++++++++++++ .../tests/tvix_tests/eval-okay-optimised-bools.exp | 1 + .../tests/tvix_tests/eval-okay-optimised-bools.nix | 21 ++++ tvix/eval/src/warnings.rs | 13 +++ 5 files changed, 165 insertions(+) create mode 100644 tvix/eval/src/compiler/optimiser.rs create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.exp create mode 100644 tvix/eval/src/tests/tvix_tests/eval-okay-optimised-bools.nix 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", } } -- cgit 1.4.1