1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64

use crate::{invariant::*, std::iter::Zip, *};

pub trait ZipExt<A: Iterator, B: Iterator> {
    #[logic]
    fn itera(self) -> A;

    #[logic]
    fn iterb(self) -> B;
}

impl<A: Iterator, B: Iterator> ZipExt<A, B> for Zip<A, B> {
    #[logic]
    #[trusted]
    #[ensures(inv(self) ==> inv(result))]
    fn itera(self) -> A {
        dead
    }

    #[logic]
    #[trusted]
    #[ensures(inv(self) ==> inv(result))]
    fn iterb(self) -> B {
        dead
    }
}

impl<A: Iterator, B: Iterator> Iterator for Zip<A, B> {
    #[open]
    #[predicate(prophetic)]
    fn completed(&mut self) -> bool {
        pearlite! {
            exists<a: &mut A, b: &mut B>
                   *a == (*self).itera() && *b == (*self).iterb()
                && ^a == (^self).itera() && ^b == (^self).iterb()
                && (a.completed() && resolve(&b)
                    || exists<x: A::Item> inv(x) && (*a).produces(Seq::singleton(x), ^a) &&
                                          resolve(&x) && (*b).completed())
        }
    }

    #[open]
    #[predicate(prophetic)]
    fn produces(self, visited: Seq<Self::Item>, o: Self) -> bool {
        pearlite! {
            // Using an `unzip` definition doesn't work well because of issues related to datatypes and `match`
            exists<p1 : Seq<_>, p2 : Seq<_>>
                   p1.len() == p2.len() && p2.len() == visited.len()
                && (forall<i :_> 0 <= i && i < visited.len() ==> visited[i] == (p1[i], p2[i]))
                && self.itera().produces(p1, o.itera()) && self.iterb().produces(p2, o.iterb())
        }
    }

    #[law]
    #[open(self)]
    #[ensures(self.produces(Seq::EMPTY, self))]
    fn produces_refl(self) {}

    #[law]
    #[open(self)]
    #[requires(a.produces(ab, b))]
    #[requires(b.produces(bc, c))]
    #[ensures(a.produces(ab.concat(bc), c))]
    fn produces_trans(a: Self, ab: Seq<Self::Item>, b: Self, bc: Seq<Self::Item>, c: Self) {}
}