val pts_to_not_null
  (#opened: _)
  (#elt: Type u#1)
  (#p: P.perm)
  (a: array elt)
  (s: Seq.seq elt)
: STGhost unit opened
    (pts_to a p s)
    (fun _ -> pts_to a p s)
    (True)
    (fun _ -> a =!= null)
let pts_to_not_null
  a s
= elim_pts_to a _ s;
  R.pts_to_not_null _ _;
  intro_pts_to a _ s
val pts_to_not_null
  (#opened: _)
  (#elt: Type u#1)
  (#p: P.perm)
  (a: array elt)
  (s: Seq.seq elt)
: STGhost unit opened
    (pts_to a p s)
    (fun _ -> pts_to a p s)
    (True)
    (fun _ -> a =!= null)
let pts_to_not_null a s =
elim_pts_to a _ s;
R.pts_to_not_null _ _;
intro_pts_to a _ s
Steel.ST.HigherArray.fst.checked
Steel.ST.PCMReference.fsti.checked Steel.ST.Loops.fsti.checked Steel.PCMMap.fst.checked Steel.PCMFrac.fst.checked Steel.Memory.fsti.checked prims.fst.checked FStar.SizeT.fsti.checked FStar.Seq.fst.checked FStar.Real.fsti.checked FStar.Pervasives.Native.fst.checked FStar.Pervasives.fsti.checked FStar.Map.fsti.checked FStar.Ghost.fsti.checked FStar.Classical.fsti.checked
Steel.ST.HigherArray.fst
Steel.Memory.inames Steel.FractionalPermission.perm Steel.ST.HigherArray.array FStar.Seq.Base.seq Steel.ST.HigherArray.intro_pts_to Steel.ST.HigherArray.mk_carrier FStar.SizeT.v FStar.Ghost.reveal FStar.SizeT.t Steel.ST.HigherArray.__proj__Mkptr__item__base_len Steel.ST.HigherArray.ptr_of Steel.ST.HigherArray.__proj__Mkptr__item__offset Prims.unit Steel.ST.PCMReference.pts_to_not_null Steel.ST.HigherArray.carrier FStar.Ghost.hide Prims.nat Steel.ST.HigherArray.pcm Steel.ST.HigherArray.__proj__Mkptr__item__base Steel.ST.HigherArray.elim_pts_to
(*
   Copyright 2022 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 Steel.ST.HigherArray

module P = Steel.PCMFrac
module R = Steel.ST.PCMReference
module M = FStar.Map
module PM = Steel.PCMMap

[@@noextract_to "krml"]
let index_t (len: Ghost.erased nat) : Tot Type0 =
  (i: nat { i < len })

[@@noextract_to "krml"]
let carrier (elt: Type u#a) (len: Ghost.erased nat) : Tot Type =
  PM.map (index_t len) (P.fractional elt)

[@@noextract_to "krml"]
let pcm (elt: Type u#a) (len: Ghost.erased nat) : Tot (P.pcm (carrier elt len)) =
  PM.pointwise (index_t len) (P.pcm_frac #elt)

[@@noextract_to "krml"]
let one (#elt: Type) (#len: Ghost.erased nat) = (pcm elt len).P.p.P.one
let composable (#elt: Type) (#len: Ghost.erased nat) = (pcm elt len).P.p.P.composable
[@@noextract_to "krml"]
let compose (#elt: Type) (#len: Ghost.erased nat) = (pcm elt len).P.p.P.op

[@@noextract_to "krml"]
let mk_carrier
  (#elt: Type)
  (len: nat)
  (offset: nat)
  (s: Seq.seq elt)
  (p: P.perm)
: Tot (carrier elt len)
= let f (i: nat) : Tot (P.fractional elt) =
    if offset + Seq.length s > len || i < offset || i >= offset + Seq.length s
    then None
    else Some (Seq.index s (i - offset), p)
  in
  M.map_literal f

let mk_carrier_inj
  (#elt: Type)
  (len: nat)
  (offset: nat)
  (s1 s2: Seq.seq elt)
  (p1 p2: P.perm)
: Lemma
  (requires (
    mk_carrier len offset s1 p1 == mk_carrier len offset s2 p2 /\
    offset + Seq.length s1 <= len /\
    offset + Seq.length s2 <= len
  ))
  (ensures (
    s1 `Seq.equal` s2 /\
    (Seq.length s1 > 0 ==> p1 == p2)
  ))
= assert (forall (i: nat) . i < Seq.length s1 ==>
    (M.sel (mk_carrier len offset s1 p1) (offset + i) == Some (Seq.index s1 i, p1)));
  assert (forall (i: nat) . i < Seq.length s2 ==>
     M.sel (mk_carrier len offset s2 p2) (offset + i) == Some (Seq.index s2 i, p2))

[@@erasable]
let base_t (elt: Type u#a) : Tot Type0 = Ghost.erased (base_len: US.t & ref _ (pcm elt (US.v base_len)))
let base_len (#elt: Type) (b: base_t elt) : GTot nat = US.v (dfst b)

[@@noextract_to "krml"]
noeq
type ptr (elt: Type u#a) : Type0 = {
  base_len: Ghost.erased US.t;
                   // U32.t to prove that A.read, A.write offset computation does not overflow. TODO: replace U32.t with size_t
  base: (r: ref _ (pcm elt (US.v base_len)) { core_ref_is_null r ==> US.v base_len == 0 });
  offset: (offset: nat { offset <= US.v base_len });
}
let null_ptr a = { base_len = 0sz; base = null #_ #(pcm a 0) ; offset = 0 }
let is_null_ptr p = is_null p.base
let base (#elt: Type) (p: ptr elt) : Tot (base_t elt) = (| Ghost.reveal p.base_len, p.base |)
let offset (#elt: Type) (p: ptr elt) : Ghost nat (requires True) (ensures (fun offset -> offset <= base_len (base p))) = p.offset

let ptr_base_offset_inj (#elt: Type) (p1 p2: ptr elt) : Lemma
  (requires (
    base p1 == base p2 /\
    offset p1 == offset p2
  ))
  (ensures (
    p1 == p2
  ))
= ()

let base_len_null_ptr _ = ()

let length_fits #elt a = ()

let valid_perm
  (len: nat)
  (offset: nat)
  (slice_len: nat)
  (p: P.perm) : Tot prop =
  let open FStar.Real in
  ((offset + slice_len <= len /\ slice_len > 0) ==> (p.P.v <=. one))

[@__reduce__]
let pts_to0 (#elt: Type u#1) (a: array elt) (p: P.perm) (s: Seq.seq elt) : Tot vprop =
  R.pts_to (ptr_of a).base (mk_carrier (US.v (ptr_of a).base_len) (ptr_of a).offset s p) `star`
  pure (
    valid_perm (US.v (ptr_of a).base_len) (ptr_of a).offset (Seq.length s) p /\
    Seq.length s == length a
  )

let pts_to (#elt: Type u#1) (a: array elt) ([@@@ smt_fallback ] p: P.perm) ([@@@ smt_fallback ] s: Seq.seq elt) : Tot vprop =
  pts_to0 a p s

// this lemma is necessary because Steel.PCMReference is marked unfold
let change_r_pts_to
  (#opened: _)
  (#carrier: Type u#1)
  (#pcm: P.pcm carrier)
  (p: ref carrier pcm)
  (v: carrier)
  (#carrier': Type u#1)
  (#pcm': P.pcm carrier')
  (p': ref carrier' pcm')
  (v': carrier')
: STGhost unit opened
    (R.pts_to p v)
    (fun _ -> R.pts_to p' v')
    (// keep on distinct lines for error messages
      carrier == carrier' /\
      pcm == pcm' /\
      p == p' /\
      v == v')
    (fun _ -> True)
= rewrite
    (R.pts_to p v)
    (R.pts_to p' v')

let intro_pts_to (#opened: _) (#elt: Type u#1) (a: array elt) (#v: _) (p: P.perm) (s: Seq.seq elt) : STGhost unit opened
  (R.pts_to (ptr_of a).base v)
  (fun _ -> pts_to a p s)
  (
    v == mk_carrier (US.v (ptr_of a).base_len) (ptr_of a).offset s p /\
    valid_perm (US.v (ptr_of a).base_len) (ptr_of a).offset (Seq.length s) p /\
    Seq.length s == length a
  )
  (fun _ -> True)
= change_r_pts_to (ptr_of a).base v (ptr_of a).base (mk_carrier (US.v (ptr_of a).base_len) (ptr_of a).offset s p);
  intro_pure _;
  rewrite
    (pts_to0 a p s)
    (pts_to a p s)

let elim_pts_to (#opened: _) (#elt: Type u#1) (a: array elt) (p: P.perm) (s: Seq.seq elt) : STGhost unit opened
  (pts_to a p s)
  (fun _ -> R.pts_to (ptr_of a).base (mk_carrier (US.v (ptr_of a).base_len) (ptr_of a).offset s p))
  (True)
  (fun _ ->
    valid_perm (US.v (ptr_of a).base_len) (ptr_of a).offset (Seq.length s) p /\
    Seq.length s == length a
  )
= rewrite
    (pts_to a p s)
    (pts_to0 a p s);
  elim_pure _

let pts_to_length
  a s
=
  elim_pts_to a _ s;
  intro_pts_to a _ s

let pts_to_not_null
val pts_to_not_null
  (#opened: _)
  (#elt: Type u#1)
  (#p: P.perm)
  (a: array elt)
  (s: Seq.seq elt)
: STGhost unit opened
    (pts_to a p s)
    (fun _ -> pts_to a p s)
    (True)
    (fun _ -> a =!= null)
a: Steel.ST.HigherArray.array elt -> s: FStar.Seq.Base.seq elt
  -> Steel.ST.Effect.Ghost.STGhost Prims.unit