Rust 数组与指针(一)

这一节主要介绍 Rust 中数组与指针的相关概念。希望通过本文,你对 Rust 有更深入的了解。

什么是数组?

数组是一组包含相同数据类型 T 的集合,存储在连续的内存区域中。理论上,内存(我们暂且不去讨论物理内存与虚拟内存)相当于一个类型为 u8、长度为 usize 的数组,内存操作相当于操作这个数组。因此,usize 可以表示每个内存地址。Rust 又规定,isize 的最大值是对象和数组大小的理论上限,这样可以确保 isize 可用于计算指向对象和数组的指针之间的差异,并可寻址对象中的每个字节及末尾的一个字节。

数组使用 [] 来创建,其大小在编译期间就已经确定,数组的类型被标记为 [T; size],表示一个类型为 Tsize个元组的数组。数组的大小是固定的,但其中的元素是可以被更改的。

接下来,我们创建一个类型为 i32,长度为8的数组,修改几个元素,并返回长度:

fn main() {
    let mut array: [i32; 8] = [0; 8];

    array[0] = 123;
    array[1] = 456;
    array[7] = 789;

    let len = array.len();
}

我们将其编译为汇编:

core::slice::<impl [T]>::len:
  sub rsp, 16
  mov qword ptr [rsp], rdi
  mov qword ptr [rsp + 8], rsi
  mov rax, qword ptr [rsp + 8]
  add rsp, 16
  ret

example::main:
  sub rsp, 40                     // 分配栈帧,rsp 寄存器存放当前函数的栈顶地址,
  lea rax, [rsp + 8]
  xor esi, esi
  mov rcx, rax
  mov rdi, rcx
  mov edx, 32
  mov qword ptr [rsp], rax
  call memset@PLT                 // 这里调用 memset 将数组的所有元素初始化为 0
  mov dword ptr [rsp + 8], 123    // 修改数组的第1个元素
  mov dword ptr [rsp + 12], 456   // 修改数组的第2个元素
  mov dword ptr [rsp + 36], 789   // 修改数组的第7个元素
  mov rax, qword ptr [rsp]
  mov rdi, rax
  mov esi, 8                      // 数组的长度是在编译时就确定的
  call qword ptr [rip + core::slice::<impl [T]>::len@GOTPCREL]
  add rsp, 40                     // 回收栈帧
  ret

你不必看懂上面的汇编代码。但是我们大概可以看到,数组的长度和内存占用大小,在编译时就已经确定。rsp + 8 为数组的地址,[rsp + 8] 就是这个地址对应的内存。瞧,在编程中操作数组,跟汇编中操作内存,很像的! 我们可以通过偏移量(索引)去操作内存中相应位置的值。

既然编译时就确定了数组的长度,如果越界访问数组,编译器会很容易检测出来:

fn main() {
    let mut array: [i32; 8] = [0; 8];

    array[10] = 123;
}
 --> <source>:4:5
  |
4 |     array[10] = 123;
  |     ^^^^^^^^^ index out of bounds: the len is 8 but the index is 10
  |

  = note: #[deny(unconditional_panic)] on by default

除了 let mut array: [i32; 8] = [0; 8]; 这种初始化数组的语法,我们还可以:

fn main() {
    let mut array: [i32; 8] = [1, 2, 3, 4, 5, 6, 7, 8];

    array[0] = 123;
    array[1] = 456;
    array[7] = 789;
}

编译成汇编后:

example::main:
  sub rsp, 32
  mov dword ptr [rsp], 1
  mov dword ptr [rsp + 4], 2
  mov dword ptr [rsp + 8], 3
  mov dword ptr [rsp + 12], 4
  mov dword ptr [rsp + 16], 5
  mov dword ptr [rsp + 20], 6
  mov dword ptr [rsp + 24], 7
  mov dword ptr [rsp + 28], 8
  mov dword ptr [rsp], 123
  mov dword ptr [rsp + 4], 456
  mov dword ptr [rsp + 28], 789
  add rsp, 32
  ret

你可以看到,这次没有调用 memset 将数组初始化为零,而是直接修改相应的元素。

数组分配在栈上,但 Rust 中,栈的大小是有限制的,取决于操作系统的限制。比如 Linux 下默认为 8M,Windows 下默认为 2M。这太小了,很多情况下这是不够用的。我们可以利用 Box,将数组分配到堆上:

fn main() {
    let mut array: Box<[i32; 1024]> = Box::new([0; 1024]);

    array[0] = 123;
    array[1] = 456;
    array[1023] = 789;
}

但是,这并不是我们期望的那样:

example::main:
  mov eax, 4120
  call __rust_probestack
  sub rsp, rax
  xor esi, esi
  lea rax, [rsp + 24]
  mov rdi, rax
  mov eax, 4096
  mov rdx, rax
  mov qword ptr [rsp + 8], rax
  call memset@PLT
  mov rdi, qword ptr [rsp + 8]
  mov esi, 4
  call alloc::alloc::exchange_malloc
  mov rcx, rax
  lea rdx, [rsp + 24]
  mov rdi, rax
  mov rsi, rdx
  mov edx, 4096
  mov qword ptr [rsp], rcx
  call memcpy@PLT
  mov rax, qword ptr [rsp]
  mov qword ptr [rsp + 16], rax
  mov rax, qword ptr [rsp + 16]
  mov dword ptr [rax], 123
  mov rax, qword ptr [rsp + 16]
  mov dword ptr [rax + 4], 456
  mov rax, qword ptr [rsp + 16]
  mov dword ptr [rax + 4092], 789
  lea rdi, [rsp + 16]
  call qword ptr [rip + core::ptr::drop_in_place@GOTPCREL]
  add rsp, 4120
  ret

这段代码首先会在栈上分配好数组,再在堆上分配内存,然后将值拷贝到堆上。修改数组元素,需要先计算出数组的地址,然后根据偏移量(索引)去修改。我们能不能将数组直接分配到堆上呢?当然是可以的,请继续往下看。

什么是指针?

指针是一个包含内存地址的变量。在 Rust 中,指针包括裸指针(*const T*mut T)、可变/不可变引用(也可以叫做借用)(&mut T&T)和智能指针(Box<T>Rc<T>Arc<T>Cell<T>RefCell<T>UnsafeCell<T> 等)。

如果获取数组的指针?

我们可以用 &&mut 操作符取得数组的引用,再用 as 操作符将引用转换为裸指针:

fn main() {
    let mut array: [i32; 3] = [1, 2, 3];

    let ref1: &[i32; 3] = &array;

    let ptr1: *const [i32; 3] = ref1 as *const [i32; 3];

    let ref2: &mut [i32; 3] = &mut array;

    let ptr2: *mut [i32; 3] = ref2 as *mut [i32; 3];
}

我们可以用 * 去解引引用和裸指针,但是解引裸指针是 unsafe 的!需要放到 unsafe {} 块中。为什么不安全?后面会讲解。

fn main() {
    let mut array: [i32; 3] = [1, 2, 3];

    let ref1: &[i32; 3] = &array;

    let ptr1: *const [i32; 3] = ref1 as *const [i32; 3];

    unsafe {
        let mut array2: [i32; 3] = *ptr1;

        array2[0] = 123;
        array2[1] = 456;
        array2[2] = 789;

        if (array == array2) {

        }
    }
}

将上面代码编译后,你会发现结果并不是你预料中的那样。虽然我们解引了 array 的裸指针 ptr1 得到了 array2,但是修改 array2 的值并不会影响到 array。由于 i32 类型是实现了 Copy[i32; 3] 也是实现了 Copy的,因此在解引的时候,会将 array复制一份。如果我们接引一个没有实现 Copy的类型:

fn main() {
    let s = String::new();

    let ptr: *const String = &s as *const String;

    unsafe {
        let s2: String = *ptr;
    }
}

这段代码是编译不过去的,编译器会告诉你:

error: src/main.rs:7: cannot move out of *ptr which is behind a raw pointer
error: src/main.rs:7: move occurs because *ptr has type std::string::String, which does not implement the Copy trait

Rust 通常情况下是不需要你手动管理内存给的,String 是一个分配在堆上的字符串类型,离开作用域后会自动释放堆内存。上面的代码,如果编译器不采取一些机制,阻止你这么做,让 ss2 指向同一块内存,当 ss2 离开作用域后,会让内存释放两次,这是不正确的。

不过编译器也提示你,将 *ptr 改为 &*ptr (help: consider borrowing here: &*ptr):

fn main() {
    let s = String::new();

    let ptr: *const String = &s as *const String;

    unsafe {
        let s2: &String = &*ptr;
    }
}

我们利用 & 将裸指针转换为了 &String。这时候,ss2 虽然指向了同一块内存,但是 s2 只是个不可变借用,并没有这块内存的所有权,只是临时借来用用,用完会还回去。

但是,问题又出来了,我们将上面的代码修改一下:

fn main() {
    let mut s = String::new();

    let ptr: *const String = &s as *const String;

    unsafe {
        let s2: &String = &*ptr;

        s.push('a');

        let len = s2.len();

        println!("{:?}", len); // 1
    }
}

根据你之前学习过的所有权的知识,上面代码是可能是无法编译通过的——可变引用与不可变引用不能同时存在(s2s的不可变引用,但是后面却修改了 s 的值)。但是,上面的代码能编译通过,并且能正确打印出 s2 的长度为1。

我们将上面代码修改成通常的方式:

fn main() {
    let mut s = String::new();

    let s2: &String = &s;

    s.push('A');

    let len = s2.len();

    println!("{:?}", len);
}

这绝对是编译不过去的:

4 |     let s2: &String = &s;
  |                       -- immutable borrow occurs here
5 |
6 |     s.push('A');
  |     ^^^^^^^^^^^ mutable borrow occurs here
7 |
8 |     let len = s2.len();
  |               -- immutable borrow later used here

为什么在那种情况下 Rust 不能保证所有权机制呢?或者是,利用裸指针突破所有权机制,会造成什么样的后果?(虽然上面那段代码符合逻辑,在其他语言中也允许那么做)

我们一开始提到 “usize 可以表示每个内存地址”,”内存是一个大数组“。没错,裸指针其实就是个 usize!它存储的值,就是内存地址。

fn main() {
    let mut s = String::new();

    let ptr: *const String = &s as *const String;
    let index: usize = ptr as usize;

    println!("{:x}", index); // 类似于 7fff0ede3988

    let ptr2: *const String = index as *const String;

    unsafe {
        let s2: &String = &*ptr2;

        s.push('a');

        let len = s2.len();

        println!("{:?}", len); // 1
    }
}

我们将裸指针转换为 usize,可以再将 usize 转换为裸指针。在转换的过程中,会丢掉上下文信息,让编译器无法判定 s2s 的不可变引用。这也为我们提供了一个豁口,得以让我们暂时突破所有权机制,去实现一些高效的数据结构。

裸指针是不安全的,在你不清楚自己在做什么时,请不要碰裸指针!在你不清楚自己在做什么时,请不要碰裸指针!在你不清楚自己在做什么时,请不要碰裸指针!

比如这段代码:

fn s_ptr() -> *const String {
    let s = "hello".to_string();
    let ptr: *const String = &s as *const String;
    ptr
}

fn main() {
    let ptr2: *const String = s_ptr();

    unsafe {
        let s2: &String = &*ptr2;

        let len = s2.len();

        println!("{:?}", len);
        println!("{}", s2); // segmentation fault (core dumped)
    }
}

Rust 会阻止你返回局部变量的引用,但是并没有阻止你返回裸指针。函数 s_ptr 中,你虽然返回出了 s 的裸指针,但是 s_ptr 调用结束后,会释放 s 的内存。ptr2 是一个悬垂指针(dangling pointer),当你解引 ptr2 得到 s2 时,s2 是一个悬垂引用(dangling references)。不过在正常的 Rust 代码中,编译器确保引用永远也不会变成悬垂状态:当你拥有一些数据的引用,编译器确保数据不会在其引用之前离开作用域 —— 前提是你不碰这些 unsafe 的东西。

可以通过裸指针修改数组吗?

当然可以!

我们先看这段代码:

fn main() {
    let array: [i32; 3] = [1, 2, 3];

    println!("{:?}", array); // [1, 2, 3]

    let ptr: *const i32 = &array as *const [i32; 3] as *const i32;

    unsafe {
        let a = ((ptr as usize) + 0) as *const i32;
        println!("{:?}", *a); // 1

        let b = ((ptr as usize) + 4) as *const i32;
        println!("{:?}", *b); // 2

        let c = ((ptr as usize) + 8) as *const i32;
        println!("{:?}", *c); // 3
    }
}

在这段代码中,我们将数组的裸指针 *const [i32; 3] 转换为 as *const i32,也就是第一个元素的地址。然后通过偏量去访问其他元素。由于 i32 类型占个字节,因此第2和第3个元素的偏移量分别是4和8。

我们再次修改代码:

fn main() {
    let array: [i32; 3] = [1, 2, 3];

    println!("{:?}", array); // [1, 2, 3]

    let ptr: *const i32 = &array as *const [i32; 3] as *const i32;

    unsafe {
        let a = ((ptr as usize) + 0) as *mut i32;

        let a2: &mut i32 = &mut *a;
        *a2 = 123;

        let b = ((ptr as usize) + 4) as *mut i32;

        let b2: &mut i32 = &mut *b;
        *b2 = 456;

        let c = ((ptr as usize) + 8) as *mut i32;

        let c2: &mut i32 = &mut *c;
        *c2 = 789;
    }

    println!("{:?}", array); // [123, 456, 789]
}

跟上面的代码不同的是,我们利用 &mut * 将裸指针转换为 &mut i32,再修改。最后打印 array,你可以看到数组已经被修改了。注意,*const T 和 *mut T 是可以利用 as 互相转换的,并不像 &mut T 能转换为 &T,而 &T 不能转换为 &mut T。虽然你可以利用裸指针作为媒介,将 &T 转换为 &mut T,在你不清楚你在做什么时,请不要这么做!

我们可以利用标准库link去简化上面的代码:

fn main() {
    let array: [i32; 3] = [1, 2, 3];

    println!("{:?}", array); // [1, 2, 3]

    let ptr: *mut i32 = &array as *const [i32; 3] as *mut i32;

    unsafe {
        println!("{:?}", ptr.add(0).read()); // 1

        ptr.add(1).write(456); // 第2个元素
    }

    println!("{:?}", array); // [1, 456, 3]
}

add 方法会帮你计算偏移量。然后用 readwrite 就可以读写相应位置的值。还要说明的是,*const T*mut T 是实现了 Copy的。

如何直接将数组分配到堆上?

Rust 标准库提供了 std::alloc::allocstd::alloc::deallocstd::alloc::realloc 等函数,对应于 C 语言的 callocfreerealloc。利用这几个函数,我们可以手动管理堆内存。

use std::alloc::{self, Layout};
use std::mem;

fn main() {
    unsafe {
        // 长度为32的i32数组
        let layout = Layout::from_size_align_unchecked(32 * mem::size_of::<i32>(), mem::size_of::<i32>());

        // 分配内存
        let ptr: *mut i32 = alloc::alloc(layout) as *mut i32;

        println!("{:?}", ptr.read());

        ptr.write(123);

        println!("{:?}", ptr.read());

        ptr.add(1).write(456);

        println!("{:?}", ptr.add(1).read());

        // 释放内存
        alloc::dealloc(ptr as *mut u8, layout);
    }
}

这段代码在堆上分配一个长度为32的 i32 数组。alloc 函数返回一个 *mut u8 指针,我们转换为 *mut i32 之后就可以想上一小节那样读写元素了。

更进一步,我们可以利用标准库提供的 slice 类型:

use std::alloc::{self, Layout};
use std::mem;
use std::slice;

fn main() {
    unsafe {
        // 长度为32的i32数组
        let layout = Layout::from_size_align_unchecked(32 * mem::size_of::<i32>(), mem::size_of::<i32>());

        // 分配内存
        let ptr: *mut i32 = alloc::alloc(layout) as *mut i32;

        let slice: &mut [i32] = slice::from_raw_parts_mut(ptr, 32);

        slice[0] = 123;
        slice[1] = 456;
        slice[2] = 789;

        println!("{:?}", slice); // [123, 456, 789, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

        println!("{:?}", &slice[..3]); // [123, 456, 789]

        // 释放内存
        alloc::dealloc(ptr as *mut u8, layout);
    }
}

利用 slice,我们可以方便的操作数组,我们不能修改切片的长度,但是可以从旧切片得到一个新切片。slice 是一个胖指针,除了指针外,还包含了长度。瞧:

struct FatPtr<T> {
    data: *const T,
    len: usize
}

我们还可以实现动态增长的数组:

use std::alloc::{self, Layout};
use std::mem;
use std::slice;

fn main() {
    unsafe {
        // 长度为32的i32数组
        let layout = Layout::from_size_align_unchecked(32 * mem::size_of::<i32>(), mem::align_of::<i32>());

        // 分配内存
        let mut ptr: *mut i32 = alloc::alloc(layout) as *mut i32;

        // 扩容
        ptr = alloc::realloc(ptr as *mut u8, layout, 64 * mem::size_of::<i32>()) as *mut i32;

        let slice: &mut [i32] = slice::from_raw_parts_mut(ptr, 64);

        slice[0] = 123;
        slice[1] = 456;
        slice[2] = 789;

        println!("{:?}", &slice[..3]); // [123, 456, 789]

        // 释放内存
        alloc::dealloc(ptr as *mut u8, layout);
    }
}

原理是这样的。我们可以继续封装一下:

use std::alloc::{self, Layout};
use std::mem;
use std::slice;
use std::ops;

pub struct MyArray<T: Sized> {
    ptr: *mut T,
    capacity: usize,
    len: usize
}

impl<T: Sized> MyArray<T> {
    pub fn with_capacity(capacity: usize) -> MyArray<T> {
        let elem_size = mem::size_of::<T>();
        let alloc_size = capacity * elem_size;
        let align = mem::align_of::<T>();

        let layout = Layout::from_size_align(alloc_size, align).unwrap();

        let ptr = unsafe {
            alloc::alloc(layout) as *mut T
        };

        MyArray {
            ptr,
            capacity,
            len: 0
        }
    }

    pub fn double(&mut self) {
        let elem_size = mem::size_of::<T>();
        let new_cap = 2 * self.capacity;
        let new_size = new_cap * elem_size;

        let align = mem::align_of::<T>();
        let size = mem::size_of::<T>() * self.capacity;
        let layout = Layout::from_size_align(size, align).unwrap();

        unsafe {
            self.ptr = alloc::realloc(self.ptr as *mut u8, layout, new_size) as *mut T;
        }

        self.capacity = new_cap;
    }

    pub fn capacity(&self) -> usize {
        self.capacity
    }

    pub fn len(&self) -> usize {
        self.len
    }

    pub fn push(&mut self, value: T) {
        if self.len == self.capacity {
            self.double()
        }

        unsafe {
            self.ptr.add(self.len).write(value);
            self.len += 1;
        }
    }

    pub fn pop(&mut self) -> Option<T> {
        if self.len == 0 {
            None
        } else {
            self.len -= 1;
            unsafe {
                Some(self.ptr.read())
            }
        }
    }

    pub fn as_slice(&self) -> &[T] {
        unsafe { slice::from_raw_parts(self.ptr, self.len) }
    }

    pub fn as_mut_slice(&self) -> &mut [T] {
        unsafe { slice::from_raw_parts_mut(self.ptr, self.len) }
    }
}

impl<T: Sized> Drop for MyArray<T> {
    fn drop(&mut self) {
        let align = mem::align_of::<T>();
        let size = mem::size_of::<T>() * self.capacity;
        let layout = Layout::from_size_align(size, align).unwrap();

        for _ in 0..self.len {
            self.pop();
        }

        unsafe {
            alloc::dealloc(self.ptr as *mut u8, layout);
        }
    }
}

impl<T> ops::Deref for MyArray<T> {
    type Target = [T];

    fn deref(&self) -> &[T] {
        self.as_slice()
    }
}

impl<T> ops::DerefMut for MyArray<T> {
    fn deref_mut(&mut self) -> &mut [T] {
        self.as_mut_slice()
    }
}

fn main() {
    let mut array: MyArray<i32> = MyArray::with_capacity(3);

    array.push(1);
    array.push(2);
    array.push(3);

    println!("{:?}", array[0]); // 1

    println!("{:?}", &array[..]); // [1, 2, 3]

    array.pop();

    println!("{:?}", &array[..]); // [1, 2]

    array.push(4);
    array.push(5);

    println!("{:?}", &array[..]); // [1, 2, 4, 5]
    println!("{:?}", array.capacity()); // 6
}

我们只实现了几个基本的方法。在 MyArray<T> 结构体中包含一个指针,capacity 表示分配的容量,len 表示当前使用的长度。添加元素时,如果容量不够,对底层数组进行扩容。我们实现了 DerefDerefMut,就可以方便的利用 slice 提供的一些方法。最后,利用 Drop 释放内存。

这不就是 Vec 嘛!

我们可以去标准库源码看 Vec 的实现,这是 Vec 的结构:

pub struct Vec<T> {
    buf: RawVec<T>,
    len: usize,
}

pub struct RawVec<T, A: Alloc = Global> {
    ptr: Unique<T>,
    cap: usize,
    a: A,
}

pub struct Unique<T: ?Sized> {
    pointer: *const T,
    _marker: PhantomData<T>,
}

Unique 是个智能指针,并不能在标准库以外的地方去使用。不过当你熟悉 Rust 的之后,你可以创建你自己的智能指针。

这一章节的内容就到这里,我们下节再见!

发表评论

电子邮件地址不会被公开。 必填项已用*标注

55 − = 46