val free_mm: #a:Type0 -> #rel:preorder a -> h:heap -> r:mref a rel{h `contains` r /\ is_mm r} -> Tot heap
let free_mm #a #rel h r =
  { h with memory = F.on_dom pos (fun r' -> if r' = r.addr then None else h.memory r') }
val free_mm: #a:Type0 -> #rel:preorder a -> h:heap -> r:mref a rel{h `contains` r /\ is_mm r} -> Tot heap
let free_mm #a #rel h r =
{ h with memory = F.on_dom pos (fun r' -> if r' = r.addr then None else h.memory r') }
FStar.Monotonic.Heap.fst.checked
prims.fst.checked FStar.Squash.fsti.checked FStar.Set.fsti.checked FStar.Preorder.fst.checked FStar.Pervasives.Native.fst.checked FStar.Pervasives.fsti.checked FStar.FunctionalExtensionality.fsti.checked FStar.ErasedLogic.fst.checked FStar.Classical.fsti.checked
FStar.Monotonic.Heap.fst
FStar.Preorder.preorder FStar.Monotonic.Heap.heap FStar.Monotonic.Heap.mref Prims.l_and FStar.Monotonic.Heap.contains Prims.b2t FStar.Monotonic.Heap.is_mm FStar.Monotonic.Heap.Mkheap_rec FStar.Monotonic.Heap.__proj__Mkheap_rec__item__next_addr FStar.FunctionalExtensionality.on_dom Prims.pos FStar.Pervasives.Native.option FStar.Pervasives.dtuple4 Prims.bool Prims.op_Equality Prims.int Prims.l_or Prims.op_GreaterThan Prims.op_GreaterThanOrEqual FStar.Monotonic.Heap.__proj__Mkcore_mref__item__addr FStar.Pervasives.Native.None FStar.Monotonic.Heap.__proj__Mkheap_rec__item__memory
(*
   Copyright 2008-2018 Microsoft Research

   Licensed under the Apache License, Version 2.0 (the "License");
   you may not use this file except in compliance with the License.
   You may obtain a copy of the License at

       http://www.apache.org/licenses/LICENSE-2.0

   Unless required by applicable law or agreed to in writing, software
   distributed under the License is distributed on an "AS IS" BASIS,
   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
   See the License for the specific language governing permissions and
   limitations under the License.
*)
module FStar.Monotonic.Heap

open FStar.Preorder
open FStar.Classical
module F = FStar.FunctionalExtensionality

private noeq type heap_rec = {
  next_addr: pos;
  memory   : F.restricted_t pos (fun (x:pos) 
             -> option (a:Type0 & rel:(option (preorder a)) & b:bool & a)) 
                      //type, preorder, mm flag, and value
}

let heap = h:heap_rec{(forall (n:nat). n >= h.next_addr ==> None? (h.memory n))}

let equal h1 h2 =
  let _ = () in
  h1.next_addr = h2.next_addr /\
  FStar.FunctionalExtensionality.feq h1.memory h2.memory

let equal_extensional h1 h2 = ()

let emp = {
  next_addr = 1;
  memory    = F.on_dom pos (fun r -> None)
}

let next_addr h = h.next_addr

noeq
type core_mref (a:Type0) : Type0 = {
  addr: (x: nat { x > 0 } );
  init: a;
  mm:   bool;  //manually managed flag
}

let addr_of #a #rel r = r.addr

let is_mm #a #rel r = r.mm

let contains #a #rel h r =
  let _ = () in
  Some? (h.memory r.addr) /\
  (let Some (| a1, pre_opt, mm, _ |) = h.memory r.addr in
   a == a1 /\ Some? pre_opt /\ Some?.v pre_opt == rel /\ mm = r.mm)  //using `===` here, since otherwise typechecker fails with a and a1 being different types, why?

let addr_unused_in n h = n <> 0 && None? (h.memory n)

let not_addr_unused_in_nullptr h = ()

let unused_in #a #rel r h = addr_unused_in (addr_of r) h

let sel_tot #a #rel h r =
  let Some (| _, _, _, x |) = h.memory r.addr in
  x

//
// We want to provide a `sel` API to the client that does not require a
//   `contains` precondition, so that the clients don't have to prove it at
//   every use of `sel`
//
// To do so, we need to be able to branch on whether the ref is contained in the heap
//
// But that's a problem since `contains` is in prop
//
// The following function assumes a boolean returning version of contains
//   We could implement is using the classical strong excluded middle axiom,
//   but we prefer to assume an specialized instance of it
//
assume val contains_bool (#a:Type0) (#rel:preorder a) (h:heap) (r:mref a rel)
  : GTot (b:bool{b <==> (h `contains` r)})

let sel #a #rel h r =
  if h `contains_bool` r
  then sel_tot #a h r
  else r.init

let upd_tot' (#a: Type0) (#rel: preorder a) (h: heap) (r: mref a rel) (x: a) =
  { h with memory = F.on_dom pos (fun r' -> if r.addr = r'
			                 then Some (| a, Some rel, r.mm, x |)
                                         else h.memory r') }

let upd_tot #a #rel h r x = upd_tot' h r x

let upd #a #rel h r x =
  if h `contains_bool` r
  then upd_tot' h r x
  else
    if r.addr >= h.next_addr
    then
      { next_addr = r.addr + 1;
        memory    = F.on_dom pos (fun r' -> if r' = r.addr
	   		                 then Some (| a, Some rel, r.mm, x |)
                                         else h.memory r') }
    else
      { h with memory = F.on_dom pos (fun r' -> if r' = r.addr
				             then Some (| a, Some rel, r.mm, x |)
                                             else h.memory r') }

let alloc #a rel h x mm =
  let r = { addr = h.next_addr; init = x; mm = mm } in
  r, { next_addr = r.addr + 1;
       memory    = F.on_dom pos (fun r' -> if r' = r.addr
	   		                then Some (| a, Some rel, r.mm, x |)
                                        else h.memory r') }
val free_mm: #a:Type0 -> #rel:preorder a -> h:heap -> r:mref a rel{h `contains` r /\ is_mm r} -> Tot heap

    h: FStar.Monotonic.Heap.heap ->
    r:
      FStar.Monotonic.Heap.mref a rel
        {FStar.Monotonic.Heap.contains h r /\ FStar.Monotonic.Heap.is_mm r}
  -> FStar.Monotonic.Heap.heap