Свързани списъци, част 2

17 ноември 2022

Административни неща

Преговор: Rc

Reference counter

Преговор: Rc

1 2 3 4 5 6 7 8 9
use std::rc::Rc;

fn main() {
    let first = Rc::new(String::from("foobar"));
    let second = Rc::clone(&first);

    println!("{}", first);
    println!("{}", second);
}
foobar foobar
use std::rc::Rc;

fn main() {
    let first = Rc::new(String::from("foobar"));
    let second = Rc::clone(&first);

    println!("{}", first);
    println!("{}", second);
}

Не позволява да взимаме mutable reference към пазената стойност

Преговор: Cell, RefCell

Преговор: RefCell

1 2 3 4 5 6 7 8 9 10 11 12 13
use std::cell::RefCell;

fn main() {
    let cell = RefCell::new(String::from("foo"));   // няма `mut`
    println!("{}", cell.borrow()); // -> Ref<String>

    {
        let mut r = cell.borrow_mut(); // -> RefMut<String>
        r.push_str("bar");
    }

    println!("{}", cell.borrow()); // -> Ref<String>
}
foo foobar
use std::cell::RefCell;

fn main() {
    let cell = RefCell::new(String::from("foo"));   // няма `mut`
    println!("{}", cell.borrow()); // -> Ref

    {
        let mut r = cell.borrow_mut(); // -> RefMut
        r.push_str("bar");
    }

    println!("{}", cell.borrow()); // -> Ref
}

Преговор: Raw pointers

1 2 3 4 5 6 7 8 9 10 11 12
let raw_const_ptr: *const u32 = &1;

unsafe {
    println!("{}", *raw_const_ptr);
}

let raw_mut_ptr: *mut u32 = &mut 1;

unsafe {
    *raw_mut_ptr += 1;
    println!("{}", *raw_mut_ptr);
}
1 2
fn main() {
let raw_const_ptr: *const u32 = &1;

unsafe {
    println!("{}", *raw_const_ptr);
}

let raw_mut_ptr: *mut u32 = &mut 1;

unsafe {
    *raw_mut_ptr += 1;
    println!("{}", *raw_mut_ptr);
}
}

Learning Rust With Entirely Too Many Linked Lists

Оригиналния източник: https://rust-unofficial.github.io/too-many-lists/

Пълния код: https://github.com/rust-unofficial/too-many-lists/tree/master/lists

Тези слайдове ще съдържат само кратки обобщения на интересни части от кода.

Persistent stack

Списък, който е напълно immutable. "Добавяне" на елемент няма, просто се конструира нов списък.

При това конструиране обаче, се споделя предишното тяло. Това означава, че, дори да създаваме "копия" на списъците, това не води до копиране на потенциално десетки хиляди елементи.

1 2 3
//  list1 -> A ---v
//  list2 ------> B -> C -> D
//  list3 -> X ---^

Още информация може да си намерите в Wikipedia, ако сте любопитни. Популярни са за езици, които наблягат на паралелизъм (haskell, erlang/elixir, clojure), понеже mutability върху shared memory е сложно в multithreaded среди.

Append

Този път не викаме take, понеже не искаме ownership -- може нещо друго да сочи към главата. Използваме Rc::clone, за да вземем наш си Rc, който сочи към същата памет.

1 2 3 4 5 6 7 8 9 10 11 12
pub struct List<T> { head: Option<Rc<Node<T>>> }

struct Node<T> { value: T, next: Option<Rc<Node<T>>>, }

pub fn append(&self, value: T) -> Self {
    let new_node = Rc::new(Node {
        value: value,
        next: self.head.as_ref().map(|node| Rc::clone(node)),
    });

    List { head: Some(new_node) }
}

Append

Спокойно можем да опростим map-а, използвайки Option::clone(). Клонирането на option просто вика clone на съдържанието му.

1 2 3 4
let new_head = self.head.as_ref().map(|node| Rc::clone(node));

// Еквивалентно на:
let new_head = self.head.clone();

Append

Вземането на опашката е интересно, понеже не използваме map, а използваме and_then

1 2 3 4 5
pub fn tail(&self) -> Self {
    List {
        head: self.head.as_ref().and_then(|rc_node| rc_node.next.clone())
    }
}

Append

С новия let-else синтаксис, може да направим и нещо друго хитро:

1 2 3 4 5 6
pub fn tail(&self) -> List<T> {
    let Some(head) = self.head.as_ref() else { return List::new() };
    let Some(next) = head.next.clone() else { return List::new() };

    List { head: Some(next) }
}

Въпрос на вкус е, но може да е по-просто от "функционалния" стил и доста ясно комуникира двата сценария, в които връщаме празен списък.

Rc::try_unwrap

Как да вземем стойност от Rc? Трудно. Трябва да имаме само един-единствен Rc, който сочи към стойността.

1 2 3 4 5
if let Ok(mut node) = Rc::try_unwrap(node) {
    // Имаме пълен ownership над истинската стойност.
} else {
    // Нещо друго някъде сочи към същата стойност. Не можем да я пипаме.
}

Drop

1 2 3 4 5 6 7 8 9 10 11 12 13
impl<T> Drop for List<T> {
    fn drop(&mut self) {
        let mut head = self.head.take();

        while let Some(node) = head {
            if let Ok(mut node) = Rc::try_unwrap(node) {
                head = node.next.take();
            } else {
                break;
            }
        }
    }
}

Проблема е, че drop-ването има същия проблем, както единичния списък: ако списъка е доста голям, то drop-ването трябва рекурсивно да деалокира неща, което може да доведе до stack overflow. Риска не е особено голям, но го има.

Горния код прави нещо доста хитро. В случай, че drop-ваме нашия списък, той започва да итерира по node-ове, и само ако това е единственото копие на node-а, го drop-ва и продължава нататък. В момента, в който се окаже, че има поне едно друго копие, деструктора спира, защото очевидно има друг списък out there, който ще се погрижи за зачистването на тази памет.

Mutable Deque

Двойносвързан списък усложнява нещата. Всеки елемент има Link напред и Link назад. Списъка има Link-ове към началото и края.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
use std::rc::Rc;
use std::cell::{RefCell, Ref};

type Link<T> = Option<Rc<RefCell<Node<T>>>>;

pub struct List<T> {
    head: Link<T>,
    tail: Link<T>,
}

struct Node<T> {
    value: T,
    next: Link<T>,
    prev: Link<T>,
}

Mutable Deque

1
type Link<T> = Option<Rc<RefCell<Node<T>>>>;

RefCell::borrow_mut

Клонирането на Option<Rc<T>> работи по същия начин. Новото е, че имаме нужда от (временен) mutable reference с borrow_mut, за да викаме методи и достъпваме атрибути на вътрешната му стойност.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
pub fn push_front(&mut self, value: T) {
    let new_head = Node::new(value) //: Rc<RefCell<Node<T>>>;

    match self.head.take() {
        Some(old_head) => {
            old_head.borrow_mut().prev = Some(new_head.clone());
            new_head.borrow_mut().next = Some(old_head);
            self.head = Some(new_head);
        },
        None => {
            self.tail = Some(new_head.clone());
            self.head = Some(new_head);
        }
    }
}

Ref

За нещастие, не можем да извадим истински reference към вътрешната стойност, и да го върнем. Методите borrow и borrow_mut не връщат &T, връщат Ref<T>

1 2 3 4 5
pub fn peek_front(&self) -> Option<Ref<T>> {
    self.head.as_ref().map(|node| {
        Ref::map(node.borrow(), |r| &r.value)
    })
}

Тъй като RefCell имплементира borrow-checker at runtime, това няма как да върне валиден reference, който е проверен at compile-time. Sadness.

Ref

Поне в случай, че имаме ownership над стойността, можем да я достъпим с into_inner. Все е нещо:

1 2 3 4 5 6
match Rc::try_unwrap(old_head) {
    Ok(cell_node) => {
        cell_node.into_inner().value
    },
    Err(_) => panic!("Popping a list failed, some Rc is messed up!"),
}

Unsafe queue

Ако искаме да имплементираме опашка, един вариант е да посегнем към unsafe pointers:

1 2 3 4 5 6 7 8 9 10 11
use std::ptr;

pub struct List<T> {
    head: *mut Node<T>,
    tail: *mut Node<T>,
}

struct Node<T> {
    value: T,
    next: *mut Node<T>,
}

В този случай, това не е чак толкова опасно, понеже го използваме в много ограничен вариант. Все пак трябва да внимаваме.

Unsafe queue

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
pub fn push(&mut self, value: T) {
    let new_tail = Box::into_raw(Box::new(Node {
        value,
        next: ptr::null_mut(),
    }));

    if !self.tail.is_null() {
        unsafe {
            (*self.tail).next = new_tail;
        }
    } else {
        self.head = new_tail;
    }

    self.tail = new_tail;
}

Алокираме си памет с Box, после веднага го разтуряме и вземаме pointer към тази памет. Единствената unsafe операция е когато дереференцираме pointer-а, за да достъпим стойността, до която сочи.

Unsafe queue

Алтернативата на това да използваме unsafe код, е да променим цялата структура на списъка, за да позволим множествен ownership над една стойност.

След като обещаем на компилатора да сме много внимателни, той е ок да ни даде стойност, която може да се занули и може да сочи към невалидна памет. Разбира се, ако сбъркаме, ще съборим програмата с един хубав segfault. В случая, риска вероятно си заслужава, но за по-сложни неща е добре внимателно да оценим предимствата и недостатъците.

Оригиналната версия на тази опашка всъщност ползваше само един pointer, но… as it turns out, това води до undefined behaviour :). Ако имате желание, може да прочетете грешната имплементация и обясненията за memory model-а на ръст и miri, но предупреждавам, че хумора става още по-интензивен: https://rust-unofficial.github.io/too-many-lists/fifth-basics.html

Въпроси