Laboratoria: 11 I¶

Manual reborrowing, visitor pattern i impl for &T¶

W tym zadaniu pokryjemy trzy niezależne tematy:

• wzorzec projektowy visitor,
• implementację traitu dla typu referencyjnego,
• manualny reborrowing.

Pracować będziemy z prostą hierarchią typów dla drzewa binarnego:

enum Node {
    Inner(InnerNode),
    Leaf(LeafNode),
}
struct InnerNode {
    value: i32,
    left: Box<Node>,
    right: Box<Node>,
}
struct LeafNode {
    value: i32,
}

Dostarczamy trait Visitor, który korzystając z metody accept typu Node umożliwi wygodne odwiedzanie węzłów drzewa:

trait Visitor {
    fn visit_inner(&mut self, node: &InnerNode);
    fn visit_leaf(&mut self, node: &LeafNode);
}

impl Node {
    fn accept<V: Visitor>(&self, visitor: &mut V) {
        match self {
            Node::Inner(inner) => visitor.visit_inner(inner),
            Node::Leaf(leaf) => visitor.visit_leaf(leaf),
        }
    }
}

1. Zaimplementuj trait Visitor dla typu TreePrinter (wartości węzłów mogą być w dowolnym porządku (pre-, in-, post-order)):

struct TreePrinter {
    ident: usize,
}
impl Visitor for TreePrinter {
    ...
}

2. Przetestuj działanie TreePrinter na przykładowym drzewie:

fn main() {
    let root = Node::Inner(InnerNode {
        ...
    });
    root.accept(&mut NodePrinter);
}

Output powinien wyglądać mniej więcej:

Inner node: 0
 Leaf node: 1
 Inner node: 2
  Leaf node: 3
  Leaf node: 4

3. Domyślnie, metody Visitor::visit_* przyjmują referencję &mut self. Dzięki temu, możemy w łatwy sposób modyfikować stan wizytora podczas odwiedzania węzłów. Niestety, może zdarzyć się sytuacja, gdy chcemy utworzyć nowy typ V implementujący Visitor, ale nie możemy pracować na obiektach typu &mut V (przykład opisany poniżej). Żeby umożliwić wszystkie możliwe przypadki, musimy zmienić sygnaturę metody Visitor::visit_* na przyjmujące self:

trait Visitor {
    fn visit_inner(self, node: &InnerNode);
    fn visit_leaf(self, node: &LeafNode);
}

Żeby utrzymać funkcjonalność z poprzedniego punktu, musimy zaimplementować Visitor dla &mut TreePrinter (zamiast dla TreePrinter) oraz delikatnie zmodyfikować metodę Node::accept:

impl Node {
    fn accept<V: Visitor>(&self, visitor: V) {
        match self {
            Node::Inner(inner) => visitor.visit_inner(inner),
            Node::Leaf(leaf) => visitor.visit_leaf(leaf),
        }
    }
}

impl Visitor for &mut TreePrinter {
    ...
}

Zastosuj zmiany i przetestuj działanie (funkcja main nie powinna ulec żadnym zmianom). Oczekiwany jest błąd kompilacji use of moved value: `self`. Napraw go używając manualnego reborrowingu (warto doczytać o tym mechanizmie w sieci).

Przykładowa sytuacja gdy nie możemy operować na obiektach typu ``&mut V``: mamy typ Interpreter , który przechodzi po AST kodu i wykonuje go. Od czasu do czasu musimy zewaluować pewne wyrażenie, co wymaga uruchomienia innego wizytora (np. Evaluator ) na tym wyrażeniu. Niestety, do ewaluacji niektórych wyrażeń (np. to wywołania funkcji) potrzebujemy rekurencyjnie wywołać interpreter, co jest niemożliwe, gdyż nie możemy mieć dwóch referencji &mut Interpreter na raz.

Rozcinanie cyklów¶

W tym zadaniu zajmiemy się rozcinaniem cyklów referencji Rc zapobiegając wyciekom pamięci.

Dana jest klasa:

#[derive(Clone)]
struct Node {
    value: &'static str,
    hard_links: RefCell<Vec<Rc<Node>>>,
    weak_links: RefCell<Vec<Weak<Node>>>,
}

impl Node {
    pub fn new(value: &'static str) -> Rc<Node> {
        Rc::new(Node {
            value,
            hard_links: RefCell::new(vec![]),
            weak_links: RefCell::new(vec![]),
        })
    }

    pub fn add_link(&self, node: Rc<Node>) {
        self.hard_links.borrow_mut().push(node);
    }
}

impl std::fmt::Debug for Node {
    fn fmt(&self, f: &mut std::fmt::Formatter) -> std::fmt::Result {
        write!(f, "{}", self.value)?;
        for link in self.hard_links.borrow().iter() {
            write!(f, "{:?}", link)?;
        }
        Ok(())
    }
}

Domyślny konstruktor - Node::new - tworzy nowy węzeł, który nie posiada żadnych połączeń. Metoda Node::add_link dodaje nowe połączenie do węzła. To połączenie jest silne, tzn. węzeł node nie może zostać usunięty, dopóki istnieje jakikolwiek węzeł, który na niego wskazuje. Możemy utworzyć graf skierowany i wydrukować jego reprezentację:

fn main() {
    let s1 = Node::new("word ");

    let s2 = Node::new("the ");
    s2.add_link(s1.clone());

    let s3 = Node::new("is ");
    s3.add_link(s2.clone());

    let s4 = Node::new("bird ");
    s4.add_link(s3.clone());

    let s5 = Node::new("the ");
    s5.add_link(s4.clone());

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

Niestety, łatwo jest utworzyć cykl referencji. Wystarczy dodać

s1.add_link(s5.clone());
println!("{:?}", s5);

i otrzymamy fatal runtime error: stack overflow.

Napisz metodę fn acycle(root: Rc<Node>) -> (), która otrzymuje źródło grafu i usuwa wszystkie cykle referencji, zamieniając minimalną liczbę linków na słabe połączenia. Przetestuj rozwiązanie na nietrywialnych przykładach.