viperproject / prusti-dev

A static verifier for Rust, based on the Viper verification infrastructure.
http://prusti.org
Other
1.52k stars 102 forks source link

`len()` implementation without overflow errors #1516

Open fpoli opened 1 month ago

fpoli commented 1 month ago

Viktor Kuncak (@vkuncak) suggested the following trick to implement a len() method that verifies with overflow checks enabled. They used it in Stainless:

impl Link {
    #[pure]
    #[ensures(result <= usize::MAX - 1)]
    fn len(&self) -> usize {
        match self {
            Link::Empty => 0,
            Link::More(node) => {
              let len1 = node.next.len();
              if len1 == usize::MAX - 1 {
                len1
              } else {
                len1 + 1
              }
            }
        }
    }
}