Iterators over slices of ZST behave strange

[RalfJung]

The following test passes for slices over non-ZST, but fails for ZST:

fn slice_test<T>(x: &[T]) {
    let mut i = x.iter();
    i.next();
    let x1 = i.next().unwrap();
    let x2 = &x[1];
    let x3 = x.iter().nth(1).unwrap();
    assert_eq!(x1 as *const _, x2 as *const _);
    assert_eq!(x2 as *const _, x3 as *const _);
}

fn main() {
    slice_test(&[1,2,3]);
    slice_test(&[(),(),()]);
}

Playpen

While pointers to ZSTs don't really matter as they will never be dereferenced, I think providing consistent addresses for the same element would still make sense.
Yet, x2 turns out to be 0x55e742ee85dc, no idea where that address is coming from. The LLVM IR contains some undef, but I am not sure if that always indicates a problem.

Generally, the iterator's treatment of ZST's seems a little fishy. Below

rust/src/libcore/slice/mod.rs

Line 777 in 4450779

impl<T> SliceIndex<[T]> for usize {

, the get methods defer to .offset to compute the address of an element of the slice. offset is only well-defined for in-bounds accesses, yet it is used here on a dangling pointer-to-ZST, with some non-0 offset.

[arielb1]

To clarify, the way the test fails is that the slice iterator returns 0x1 instead of an actual pointer to an element.

[arielb1]

Generally, the iterator's treatment of ZST's seems a little fishy. Below

rust/src/libcore/slice/mod.rs

Line 777 in 4450779

impl<T> SliceIndex<[T]> for usize {

, the get methods defer to .offset to compute the address of an element of the slice. offset is only well-defined for in-bounds accesses, yet it is sued here on a dangling pointer-to-ZST, with some non-0 offset.

By "dangling element" you mean 0x8: &mut Zst? By what I was able to read from LLVM's rules, a "valid pointer range" for the purpose of GEPi is just a range that:
A) does not start or contain null or ~0.
B) does not overlap with any "LLVM-known allocation" - aka globals, stack, malloc, etc.

In particular, LLVM does not try to know about all allocas in address space, it only cares about the ones it knows about, so 0x8 is a valid pointer.

[RalfJung]

To clarify, the way the test fails is that the slice iterator returns 0x1 instead of an actual pointer to an element.

IMHO that would be fine, if the get methods did the same. Things just should be consistent.

By "dangling element" you mean 0x8: &mut Zst?

0x1 here, but yeah.

[oli-obk]

We could treat any cast to a raw pointer to a zst as a constant producing an integer. Should be trivial to do as a Mir pass and has clear semantics imo.

[RalfJung]

This can't be done on polymorphic code though, can it?

[strega-nil]

@arielb1 Could you show where LLVM talks about treating ~0 specially?

[bluss]

I was going to fix this for the slice iterator in #46223, but I have yet to pick it up again (feel free to do that anyone).

[RalfJung]

Thanks to @rkruppe for pointing out that this is actually a soundness issue. The following module should never panic:

mod unique_token {
    use std::sync::atomic::{AtomicBool, Ordering};

    // With a private field so it can only be constructed inside this module
    pub struct Token(());
    
    // Stores whether we have already created a token
    static GUARD : AtomicBool = AtomicBool::new(false);
    
    impl Token {
        pub fn new() -> Option<Token> {
            if GUARD.compare_and_swap(false, true, Ordering::AcqRel) == false {
                Some(Token(()))
            } else {
                None
            }
        }
        
        pub fn take_two(a: &Token, b: &Token) {
            // There's only ever one token so these have to be the same
            assert_eq!(a as *const _, b as *const _,
                "How can there be two tokes?!?");
        }
    }
}

and yet here is how we can make it panic:

use unique_token::Token;

fn main() {
    let t = Token::new().expect("Couldn't even get a single token");
    // make sure we can't get a second
    assert!(Token::new().is_none());
    
    let s = &[t];
    let t1 = &s[0];
    let t2 = s.iter().next().expect("Slice can't be empty");
    Token::take_two(t1, t2);
}

Playground

[arielb1]

@RalfJung

You can also get elements of slices through slice patterns, which don't squash ZST pointers to 0x1. You have a good argument for having slice iterators use the "real" address of the ZST instead of squashing it.

cc @rust-lang/libs - what's the obstacle to not squashing pointers in iterators?

[arielb1]

Not sure whether we should tag this as I-unsound

[RalfJung]

The iterators also play fast-and-loose with the alignment rules. For example, Iter::as_slice will call from_raw_parts with an unaligned pointer when used with a type like [u32; 0].

[RalfJung]

I have a proposed fix at #52206.