rust raw pointer not working without a println!() statement

Question

Today i try to use unsafe code to resolve a test, but encountered a weird problem, I found unrelated statement will affect the behavior of unsafe code. below is my code:

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
  pub val: i32,
  pub next: Option<Box<ListNode>>
}

impl ListNode {
  #[inline]
  fn new(val: i32) -> Self {
    ListNode {
      next: None,
      val
    }
  }
}

use rand;
use std::ptr::null;


struct Solution {
    list: Option<Box<ListNode>>,
    ptr: *const Option<Box<ListNode>>
}


impl Solution {
    fn new(head: Option<Box<ListNode>>) -> Self {
        let mut s = Self {
            list: head,
            ptr: null(),
        };
        s.ptr = &s.list as *const Option<Box<ListNode>>;
        s
    }
    
    fn get_random(&mut self) -> i32 {
        // generate random jumps
        let mut jumps: u8 = rand::random();
        unsafe {
            // if self.ptr is not point to the last node, update self.ptr to point next node
            // else point to head
            while jumps > 0 {
                if (*self.ptr).as_ref().unwrap().next.is_some() {
                    self.ptr = &(*self.ptr).as_ref().unwrap().next as *const Option<Box<ListNode>>;
                } else {
                    self.ptr = &self.list as *const Option<Box<ListNode>>;
                }
                jumps -= 1;
                // if comment below statement, the result will be like:
                // results: [573225736, 573225736, 573225736, 573225736]
                // if uncomment this statement, the result will be like:
                // results: [1, 2, 2, 1]
                // obviously the later one is correct
                println!("{}", jumps);
            }
            return (*self.ptr).as_ref().unwrap().val;
        }
    }
}


fn main() {
    let mut s = Solution::new(Some(Box::new(ListNode{
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode {
                val: 3,
                next: None,
            }))
        }))
    })));
    let mut res = Vec::new();
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    println!("results: {:?}", res);
}

Why is the result related to a println!() statement? It's so weird. Is there anyone can explain this for me?

Answer 1

You can use the MIRI tool to check for undefined behavior and other problems when using unsafe. I guess it won't catch all problems, yet it's still incredibly useful. Currently it's available only in nightly, but it's very easy to use via the rust playground:

error: Undefined Behavior: pointer to alloc1603 was dereferenced after this allocation got freed
  --> src/main.rs:45:20
   |
45 |                 if (*self.ptr).as_ref().unwrap().next.is_some() {
   |                    ^^^^^^^^^^^ pointer to alloc1603 was dereferenced after this allocation got freed
   |
   = help: this indicates a bug in the program: it performed an invalid operation, and caused Undefined Behavior
   = help: see https://doc.rust-lang.org/nightly/reference/behavior-considered-undefined.html for further information

As some comments have suggested you are storing the pointer to an Option (which can move) instead of the Box which cannot. If you change

    ptr: *const Option<Box<ListNode>>

to

    ptr: Option<*const ListNode>,

you will avoid the problem. This can be verified by MIRI, which no longer emits an error message:

// Definition for singly-linked list.
#[derive(PartialEq, Eq, Clone, Debug)]
pub struct ListNode {
    pub val: i32,
    pub next: Option<Box<ListNode>>,
}

impl ListNode {
    #[inline]
    fn new(val: i32) -> Self {
        ListNode { next: None, val }
    }
}

use rand;
use std::ptr::null;

struct Solution {
    list: Option<Box<ListNode>>,
    ptr: Option<*const ListNode>,
}

impl Solution {
    fn new(head: Option<Box<ListNode>>) -> Self {
        let p = match &head {
            None => None,
            Some(h) => Some(&**h as *const ListNode),
        };

        let mut s = Self { list: head, ptr: p };
        s
    }

    fn get_random(&mut self) -> i32 {
        // generate random jumps
        let mut jumps: u8 = rand::random();
        unsafe {
            // if self.ptr is not point to the last node, update self.ptr to point next node
            // else point to head
            while jumps > 0 {
                if let Some(p) = self.ptr {
                    self.ptr = match &(*p).next {
                        None => Some(&**self.list.as_ref().unwrap() as *const ListNode),
                        Some(n) => Some(&**n as *const ListNode),
                    };
                }

                jumps -= 1;
                // if comment below statement, the result will be like:
                // results: [573225736, 573225736, 573225736, 573225736]
                // if uncomment this statement, the result will be like:
                // results: [1, 2, 2, 1]
                // obviously the later one is correct
                println!("{}", jumps);
            }
            return (*(self.ptr.unwrap())).val;
        }
    }
}

fn main() {
    let mut s = Solution::new(Some(Box::new(ListNode {
        val: 1,
        next: Some(Box::new(ListNode {
            val: 2,
            next: Some(Box::new(ListNode { val: 3, next: None })),
        })),
    })));
    let mut res = Vec::new();
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    res.push(s.get_random());
    println!("results: {:?}", res);
}

PS: your code assumes that the list passed to new() will never be None and bad things can happen in that case :)