// RUN: @caesar @file --quantifier-instantiation e-matching

// Verification of Rabin's mutual exclusion algorithm, based on
//      Joe Hurd, Annabelle McIver, Carroll Morgan: Probabilistic Guarded Commands Mechanized in HOL. QAPL 2004: 95-111
//      https://doi.org/10.1016/j.entcs.2004.01.021

domain Exponentials {
    func rec_pown_2(exponent: UInt): UReal = ite(exponent == 0, 1, rec_pown_2(exponent - 1) / 2)
}

@wlp
proc rabin(init_i: UInt) -> (i: UInt)
    pre [init_i == 1] + [init_i > 1] * (2/3)
    post [i == 1]
{
    i = init_i
    // One survivor contributes 1, no survivors contribute 0, and another round contributes 2/3.
    @invariant([i == 1] + [i > 1] * (2/3))
    while i > 1 {
        // Each contender present at the start of this round flips exactly once.
        var n: UInt = i
        // Evaluate the outer annotation after the remaining n flips.
        @invariant(
            [n <= i] * (
                // More than one eventual survivor contributes 2/3.
                (2/3) * (1 - ([i == n] * (n + 1) + [i == n + 1]) * rec_pown_2(n))
                // Exactly one eventual survivor contributes 1.
                + ([i == n] * n + [i == n + 1]) * rec_pown_2(n)
            )
        )
        while n > 0 {
            var withdraw: Bool = flip(0.5)
            if withdraw {
                i = i - 1
            } else {}
            n = n - 1
        }
    }
}
