Support tail calls in the interpreter

10 files changed, 281 insertions, 1 deletions

diff --git a/compiler/rustc_const_eval/src/interpret/terminator.rs b/compiler/rustc_const_eval/src/interpret/terminator.rs
index 7d1a48d6ded..d77bcdd7097 100644
--- a/compiler/rustc_const_eval/src/interpret/terminator.rs
+++ b/compiler/rustc_const_eval/src/interpret/terminator.rs
@@ -172,7 +172,77 @@ impl<'tcx, M: Machine<'tcx>> InterpCx<'tcx, M> {
                 }
             }
 
-            TailCall { func: _, args: _, fn_span: _ } => todo!(),
+            TailCall { ref func, ref args, fn_span: _ } => {
+                // FIXME(explicit_tail_calls): a lot of code here is duplicated with normal calls, can we refactor this?
+                let old_frame_idx = self.frame_idx();
+                let func = self.eval_operand(func, None)?;
+                let args = self.eval_fn_call_arguments(args)?;
+
+                let fn_sig_binder = func.layout.ty.fn_sig(*self.tcx);
+                let fn_sig =
+                    self.tcx.normalize_erasing_late_bound_regions(self.param_env, fn_sig_binder);
+                let extra_args = &args[fn_sig.inputs().len()..];
+                let extra_args =
+                    self.tcx.mk_type_list_from_iter(extra_args.iter().map(|arg| arg.layout().ty));
+
+                let (fn_val, fn_abi, with_caller_location) = match *func.layout.ty.kind() {
+                    ty::FnPtr(_sig) => {
+                        let fn_ptr = self.read_pointer(&func)?;
+                        let fn_val = self.get_ptr_fn(fn_ptr)?;
+                        (fn_val, self.fn_abi_of_fn_ptr(fn_sig_binder, extra_args)?, false)
+                    }
+                    ty::FnDef(def_id, substs) => {
+                        let instance = self.resolve(def_id, substs)?;
+                        (
+                            FnVal::Instance(instance),
+                            self.fn_abi_of_instance(instance, extra_args)?,
+                            instance.def.requires_caller_location(*self.tcx),
+                        )
+                    }
+                    _ => span_bug!(
+                        terminator.source_info.span,
+                        "invalid callee of type {:?}",
+                        func.layout.ty
+                    ),
+                };
+
+                // This is the "canonical" implementation of tails calls,
+                // a pop of the current stack frame, followed by a normal call
+                // which pushes a new stack frame, with the return address from
+                // the popped stack frame.
+                //
+                // Note that we can't use `pop_stack_frame` as it "executes"
+                // the goto to the return block, but we don't want to,
+                // only the tail called function should return to the current
+                // return block.
+                let Some(prev_frame) = self.stack_mut().pop() else {
+                    span_bug!(
+                        terminator.source_info.span,
+                        "empty stack while evaluating this tail call"
+                    )
+                };
+
+                let StackPopCleanup::Goto { ret, unwind } = prev_frame.return_to_block else {
+                    span_bug!(terminator.source_info.span, "tail call with the root stack frame")
+                };
+
+                self.eval_fn_call(
+                    fn_val,
+                    (fn_sig.abi, fn_abi),
+                    &args,
+                    with_caller_location,
+                    &prev_frame.return_place,
+                    ret,
+                    unwind,
+                )?;
+
+                if self.frame_idx() != old_frame_idx {
+                    span_bug!(
+                        terminator.source_info.span,
+                        "evaluating this tail call pushed a new stack frame"
+                    );
+                }
+            }
 
             Drop { place, target, unwind, replace: _ } => {
                 let place = self.eval_place(place)?;
diff --git a/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.rs b/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.rs
new file mode 100644
index 00000000000..5a105ee4eb5
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.rs
@@ -0,0 +1,14 @@
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+pub const fn test(_: &Type) {
+    const fn takes_borrow(_: &Type) {}
+
+    let local = Type;
+    become takes_borrow(&local);
+    //~^ error: `local` does not live long enough
+}
+
+struct Type;
+
+fn main() {}
diff --git a/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.stderr b/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.stderr
new file mode 100644
index 00000000000..75fb13c378c
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-arg-bad-borrow.stderr
@@ -0,0 +1,14 @@
+error[E0597]: `local` does not live long enough
+  --> $DIR/ctfe-arg-bad-borrow.rs:8:25
+   |
+LL |     let local = Type;
+   |         ----- binding `local` declared here
+LL |     become takes_borrow(&local);
+   |                         ^^^^^^ borrowed value does not live long enough
+LL |
+LL | }
+   | - `local` dropped here while still borrowed
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0597`.
diff --git a/tests/ui/explicit-tail-calls/ctfe-arg-good-borrow.rs b/tests/ui/explicit-tail-calls/ctfe-arg-good-borrow.rs
new file mode 100644
index 00000000000..50bf6c946ca
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-arg-good-borrow.rs
@@ -0,0 +1,13 @@
+//@ check-pass
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+pub const fn test(x: &Type) {
+    const fn takes_borrow(_: &Type) {}
+
+    become takes_borrow(x);
+}
+
+pub struct Type;
+
+fn main() {}
diff --git a/tests/ui/explicit-tail-calls/ctfe-arg-move.rs b/tests/ui/explicit-tail-calls/ctfe-arg-move.rs
new file mode 100644
index 00000000000..88ff3a4a5ad
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-arg-move.rs
@@ -0,0 +1,15 @@
+//@ check-pass
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+pub const fn test(s: String) -> String {
+    const fn takes_string(s: String) -> String {
+        s
+    }
+
+    become takes_string(s);
+}
+
+struct Type;
+
+fn main() {}
diff --git a/tests/ui/explicit-tail-calls/ctfe-collatz-multi-rec.rs b/tests/ui/explicit-tail-calls/ctfe-collatz-multi-rec.rs
new file mode 100644
index 00000000000..2e6bb0e1ac5
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-collatz-multi-rec.rs
@@ -0,0 +1,43 @@
+//@ run-pass
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+/// A very unnecessarily complicated "implementation" of the callatz conjecture.
+/// Returns the number of steps to reach `1`.
+///
+/// This is just a test for tail calls, which involves multiple functions calling each other.
+///
+/// Panics if `x == 0`.
+const fn collatz(x: u32) -> u32 {
+    assert!(x > 0);
+
+    const fn switch(x: u32, steps: u32) -> u32 {
+        match x {
+            1 => steps,
+            _ if x & 1 == 0 => become div2(x, steps + 1),
+            _ => become mul3plus1(x, steps + 1),
+        }
+    }
+
+    const fn div2(x: u32, steps: u32) -> u32 {
+        become switch(x >> 1, steps)
+    }
+
+    const fn mul3plus1(x: u32, steps: u32) -> u32 {
+        become switch(3 * x + 1, steps)
+    }
+
+    switch(x, 0)
+}
+
+const ASSERTS: () = {
+    assert!(collatz(1) == 0);
+    assert!(collatz(2) == 1);
+    assert!(collatz(3) == 7);
+    assert!(collatz(4) == 2);
+    assert!(collatz(6171) == 261);
+};
+
+fn main() {
+    let _ = ASSERTS;
+}
diff --git a/tests/ui/explicit-tail-calls/ctfe-id-unlimited.return.stderr b/tests/ui/explicit-tail-calls/ctfe-id-unlimited.return.stderr
new file mode 100644
index 00000000000..4a1e50b4111
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-id-unlimited.return.stderr
@@ -0,0 +1,36 @@
+error[E0080]: evaluation of constant value failed
+  --> $DIR/ctfe-id-unlimited.rs:17:42
+   |
+LL |             #[cfg(r#return)] _ => return inner(acc + 1, n - 1),
+   |                                          ^^^^^^^^^^^^^^^^^^^^^ reached the configured maximum number of stack frames
+   |
+note: inside `inner`
+  --> $DIR/ctfe-id-unlimited.rs:17:42
+   |
+LL |             #[cfg(r#return)] _ => return inner(acc + 1, n - 1),
+   |                                          ^^^^^^^^^^^^^^^^^^^^^
+note: [... 125 additional calls inside `inner` ...]
+  --> $DIR/ctfe-id-unlimited.rs:17:42
+   |
+LL |             #[cfg(r#return)] _ => return inner(acc + 1, n - 1),
+   |                                          ^^^^^^^^^^^^^^^^^^^^^
+note: inside `rec_id`
+  --> $DIR/ctfe-id-unlimited.rs:22:5
+   |
+LL |     inner(0, n)
+   |     ^^^^^^^^^^^
+note: inside `ID_ED`
+  --> $DIR/ctfe-id-unlimited.rs:29:20
+   |
+LL | const ID_ED: u32 = rec_id(ORIGINAL);
+   |                    ^^^^^^^^^^^^^^^^
+
+note: erroneous constant encountered
+  --> $DIR/ctfe-id-unlimited.rs:31:40
+   |
+LL | const ASSERT: () = assert!(ORIGINAL == ID_ED);
+   |                                        ^^^^^
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0080`.
diff --git a/tests/ui/explicit-tail-calls/ctfe-id-unlimited.rs b/tests/ui/explicit-tail-calls/ctfe-id-unlimited.rs
new file mode 100644
index 00000000000..54e68b2b7f7
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-id-unlimited.rs
@@ -0,0 +1,35 @@
+//@ revisions: become return
+//@ [become] run-pass
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+// This is an identity function (`|x| x`), but implemented using recursion.
+// Each step we increment accumulator and decrement the number.
+//
+// With normal calls this fails compilation because of the recursion limit,
+// but with tail calls/`become` we don't grow the stack/spend recursion limit
+// so this should compile.
+const fn rec_id(n: u32) -> u32 {
+    const fn inner(acc: u32, n: u32) -> u32 {
+        match n {
+            0 => acc,
+            #[cfg(r#become)] _ => become inner(acc + 1, n - 1),
+            #[cfg(r#return)] _ => return inner(acc + 1, n - 1),
+            //[return]~^ error: evaluation of constant value failed
+        }
+    }
+
+    inner(0, n)
+}
+
+// Some relatively big number that is higher than recursion limit
+const ORIGINAL: u32 = 12345;
+// Original number, but with identity function applied
+// (this is the same, but requires execution of the recursion)
+const ID_ED: u32 = rec_id(ORIGINAL);
+// Assert to make absolutely sure the computation actually happens
+const ASSERT: () = assert!(ORIGINAL == ID_ED);
+
+fn main() {
+    let _ = ASSERT;
+}
diff --git a/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.rs b/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.rs
new file mode 100644
index 00000000000..3d69cde2989
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.rs
@@ -0,0 +1,19 @@
+#![allow(incomplete_features)]
+#![feature(explicit_tail_calls)]
+
+pub const fn f() {
+    become g();
+}
+
+const fn g() {
+    panic!()
+    //~^ error: evaluation of constant value failed
+    //~| note: in this expansion of panic!
+    //~| note: inside `g`
+    //~| note: in this expansion of panic!
+}
+
+const _: () = f();
+//~^ note: inside `_`
+
+fn main() {}
diff --git a/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.stderr b/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.stderr
new file mode 100644
index 00000000000..8c070512105
--- /dev/null
+++ b/tests/ui/explicit-tail-calls/ctfe-tail-call-panic.stderr
@@ -0,0 +1,21 @@
+error[E0080]: evaluation of constant value failed
+  --> $DIR/ctfe-tail-call-panic.rs:9:5
+   |
+LL |     panic!()
+   |     ^^^^^^^^ the evaluated program panicked at 'explicit panic', $DIR/ctfe-tail-call-panic.rs:9:5
+   |
+note: inside `g`
+  --> $DIR/ctfe-tail-call-panic.rs:9:5
+   |
+LL |     panic!()
+   |     ^^^^^^^^
+note: inside `_`
+  --> $DIR/ctfe-tail-call-panic.rs:16:15
+   |
+LL | const _: () = f();
+   |               ^^^
+   = note: this error originates in the macro `$crate::panic::panic_2015` which comes from the expansion of the macro `panic` (in Nightly builds, run with -Z macro-backtrace for more info)
+
+error: aborting due to 1 previous error
+
+For more information about this error, try `rustc --explain E0080`.