This can be implemented with tail calls (unstable feature as of now) but with some difficulty. Presented is the full solution.
#![expect(incomplete_features)]
#![feature(explicit_tail_calls)]
struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
fn drop(&mut self) {
println!("Dropping #{}", self.0);
}
}
// The list is actually defined as usual.
struct LinkedList {
now: ScreamOnDrop,
// any data fields can be added here...
next: Option<Box<LinkedList>>
}
impl LinkedList {
// Now, we get to something unusual.
// We are going to tail call dropping the next list element.
// It must have signature of Fn(LinkedList) -> ().
// Therefore, we cannot call it from anything but Fn(LinkedList) -> ();
// this mandates a `Self::drop` inherent function.
fn drop(mut self) {
if let Some(tail) = self.next.take() {
// We got a Box<LinkedList>. It does not have inherent `drop` so
// we must dereference it.
let tail: LinkedList = *tail;
// Before the call starts, every other field in `self` is dropped.
become tail.drop()
}
// else { panic!("uncomment to see that stack does not grow") }
}
}
// We need to route Drop implementation to the inherent function.
// `Drop::drop` only gives us a mutable reference, so only elements from
// the 2nd onwards will be dropped through inherent `LinkedList::drop`.
impl Drop for LinkedList {
fn drop(&mut self) {
// Checking if there is any list tail.
// Other fields will be handled by the compiler automatically.
if let Some(tail) = self.next.take() {
(*tail).drop(); // tail call conditions are not met here
}
}
}
fn main() {
let mut list = None;
for i in 0..5 {
let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
list = Some(Box::new(next_node));
}
}
It has somewhat unusual drop order:
Dropping #1
Dropping #2
Dropping #3
Dropping #4
Dropping #0
1 Like
I think that should be equivalent to the following (which doesn't use unstable features):
struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
fn drop(&mut self) {
println!("Dropping #{}", self.0);
}
}
// The list is actually defined as usual.
struct LinkedList {
now: ScreamOnDrop,
// any data fields can be added here...
next: Option<Box<LinkedList>>
}
impl Drop for LinkedList {
fn drop(&mut self) {
println!("I was called. Empty tail? {}", self.next.is_none());
while let Some(mut tail) = self.next.take() {
self.next = tail.next.take();
}
}
}
fn main() {
let mut list = None;
for i in 0..5 {
let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
list = Some(Box::new(next_node));
}
println!("End of main");
}
(I added some printlns to see what happens. It has the same drop order as yours AFAICT.)
5 Likes
Thank you! Turns out I've forgotten that dereference might be an expensive operation if lots of data are moved out of the Box...
This should work better, with ScreamOnDrop being dropped in-place.
#![expect(incomplete_features)]
#![feature(explicit_tail_calls)]
struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
fn drop(&mut self) {
println!("Dropping #{}", self.0);
}
}
// The list is actually defined as usual.
struct LinkedList {
now: ScreamOnDrop,
// any data fields can be added here...
next: Option<Box<LinkedList>>
}
trait FastDrop {
fn drop(self);
}
impl FastDrop for Box<LinkedList> {
// Now, we get to something unusual.
// We are going to tail call dropping the next list element.
// It must have signature of Fn(Box<LinkedList>) -> ().
// Therefore, we cannot call it from anything but Fn(Box<LinkedList>) -> ();
// this mandates a `Box<LinkedList>::drop` function.
// It cannot be inherent (orphan rule) so we have a trait.
fn drop(mut self) {
if let Some(tail) = self.next.take() {
// Before the call starts, every other field in `self` is dropped.
become tail.drop()
}
// else { panic!("uncomment to see that stack does not grow") }
}
}
// We need to route Drop implementation to the appropriate function.
// `Drop::drop` only gives us a mutable reference, so only elements from
// the 2nd onwards will be dropped through trait's `FastDrop::drop`.
impl Drop for LinkedList {
fn drop(&mut self) {
// Checking if there is any list tail.
// Other fields will be handled by the compiler automatically.
if let Some(tail) = self.next.take() {
tail.drop(); // tail call conditions are not met here
}
}
}
fn main() {
let mut list = None;
for i in 0..5 {
let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
list = Some(Box::new(next_node));
}
}
My intent was actually to showcase tail calls on this use case (it has better separation of responsibilities).
1 Like
Here is a simple implementation with an intuitive order and without additional traits:
struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
fn drop(&mut self) {
println!("Dropping #{}", self.0);
}
}
struct LinkedList {
now: ScreamOnDrop,
// any data fields can be added here...
next: Option<Box<LinkedList>>
}
impl Drop for LinkedList {
fn drop(&mut self) {
while let Some(next) = self.next.take() {
*self = *next;
}
}
}
fn main() {
let mut list = None;
for i in 0..5 {
let next_node = LinkedList { now: ScreamOnDrop(5 - i), next: list };
list = Some(Box::new(next_node));
}
}
It has however the downside of moving every element, which can be potentially costly.
If you however separate LinkedList and Node (which you probably want to do anyway, otherwise you end up with the list always containing at least one element, and with that element living in the "stack" portion of the linked list), then you can avoid that:
struct ScreamOnDrop(i32);
impl Drop for ScreamOnDrop {
fn drop(&mut self) {
println!("Dropping #{}", self.0);
}
}
struct LinkedList {
head: Option<Box<Node>>,
}
struct Node {
now: ScreamOnDrop,
// any data fields can be added here...
next: Option<Box<Node>>
}
impl Drop for LinkedList {
fn drop(&mut self) {
while let Some(mut node) = self.head.take() {
self.head = node.next.take();
}
}
}
fn main() {
let mut list = LinkedList { head: None };
for i in 0..5 {
let next_node = Node { now: ScreamOnDrop(5 - i), next: list.head.take() };
list.head = Some(Box::new(next_node));
}
}
1 Like