AeneasVerif / aeneas

A verification toolchain for Rust programs
Apache License 2.0
196 stars 15 forks source link

Failure when extracting a loop with a shared borrow #134

Open RaitoBezarius opened 7 months ago

RaitoBezarius commented 7 months ago

https://github.com/RaitoBezarius/avl-verification/commit/117cd1c0afbc50ffc5a90473cb4c01185188711e fails extraction with Aeneas:

❯ nix run github:aeneasverif/aeneas -L -- -backend lean avl_verification.llbc
[Info ] Imported: avl_verification.llbc
[Info ] Generated the partial file (because of errors): ./AvlVerification.lean
[Error] There should be no bottoms in the value
Source: 'src/main.rs', lines 33:52-39:9

related to the find function.

sonmarcho commented 6 months ago

Slightly minimized example:

struct AVLNode {
    child: Option<Box<AVLNode>>,
}

struct AVLTreeSet {
    root: Option<Box<AVLNode>>,
}

impl AVLNode {
    pub fn find(self) -> bool {
        let mut current_tree = &self.child; // This is the root of the problem in the computation of the fixed point

        while let Some(current_node) = current_tree {
            current_tree = &current_node.child;
        }

        false
    }
}