source: src/joint/BEValues.ma @ 1300

(* Type of values used in the dynamic semantics of the back-end intermediate
   languages. Inspired by common/Values.ma, adapted from Compcert *)

include "common/Pointers.ma".

record part (r: region): Type[0] ≝
 { part_no:> nat
 ; part_no_ok: part_no ≤ size_pointer r
 }.

(* Byte-sized values used in the back-end.
   Values larger than a single Byte are represented via their parts.
   Values are either:
  - machine integers (Bytes)
  - parts of a pointer seen as a triple giving the representation of the
    pointer (in terms of the memory regions such a pointer could address),
    a memory address and an integer offset with respect to this address;
  - a null pointer: the region denotes the pointer size
  - the [BVundef] value denoting an arbitrary bit pattern, such as the
    value of an uninitialized variable
*)

inductive beval: Type[0] ≝
  | BVundef: beval
  | BVByte: Byte → beval
  | BVnull: ∀r:region. part r → beval
  | BVptr: ∀p:pointer. part (ptype p) → beval.

definition eq_beval: beval → beval → bool ≝
 λv1,v2.
  match v1 with
   [ BVundef      ⇒ match v2 with [ BVundef      ⇒ true                           | _ ⇒ false ]
   | BVByte b1    ⇒ match v2 with [ BVByte b2    ⇒ eq_bv … b1 b2                  | _ ⇒ false ]
   | BVnull r1 p1 ⇒ match v2 with [ BVnull r2 p2 ⇒ eq_region … r1 r2 ∧ eqb p1 p2  | _ ⇒ false ]
   | BVptr P1 p1  ⇒ match v2 with [ BVptr P2 p2  ⇒ eq_pointer … P1 P2 ∧ eqb p1 p2 | _ ⇒ false ]].

axiom CorruptedValue: String.

let rec pointer_of_bevals_aux (p:pointer) (part: nat) (l: list beval) on l : res pointer ≝
 match l with
  [ nil ⇒
     if eqb part (size_pointer (ptype p)) then
      OK … p
     else
      Error … [MSG CorruptedValue]
  | cons v tl ⇒
     match v with
      [ BVptr p' part' ⇒
         if eq_pointer p p' ∧ eqb part part' then
          pointer_of_bevals_aux p (S part) tl
         else
          Error … [MSG CorruptedValue]
      | _ ⇒ Error … [MSG CorruptedValue]]].

axiom NotAPointer: String.

(* CSC: use vectors in place of lists? Or even better products of tuples
   (more easily pattern matchable in the finite case)? requires one more parameter *)
definition pointer_of_bevals: list beval → res pointer ≝
 λl.
 match l with
  [ nil ⇒ Error … [MSG NotAPointer]
  | cons he tl ⇒
     match he with
      [ BVptr p part ⇒
         if eqb part 0 then pointer_of_bevals_aux p 1 tl else Error … [MSG NotAPointer]
      | _ ⇒ Error … [MSG NotAPointer]]].

(* CSC: use vectors in place of lists? Or even better products of tuples
   (more easily pattern matchable in the finite case)? *)
let rec bevals_of_pointer_aux (p:pointer) (part: nat) (n: nat) (pr: plus part n = size_pointer (ptype p)) on n: list beval ≝
 match n with
  [ O ⇒ λ_.[]
  | S m ⇒ λpr':n=S m.(BVptr p (mk_part … part …))::bevals_of_pointer_aux p (S part) m ?] (refl ? n).
/3/ qed.

definition bevals_of_pointer: pointer → list beval ≝
 λp. bevals_of_pointer_aux p 0 (size_pointer (ptype p)) ….
// qed.

lemma pointer_of_bevals_bevals_of_pointer:
 ∀p. pointer_of_bevals (bevals_of_pointer p) = OK … p.
* * #pbl #pok #poff
try %
whd in ⊢ (??%?) >reflexive_eq_pointer >(eqb_n_n 1) [2,3: %]
whd in ⊢ (??%?) >reflexive_eq_pointer >(eqb_n_n 2) %
qed.

(* CSC: move elsewhere *)
(* CSC: Wrong data-type? Use products of products *)
definition list_to_pair: ∀A:Type[0]. ∀l:list A. length … l = 2 → A × A.
 #A #l cases l [2: #a #tl cases tl [2: #b #tl' cases tl' [1: #_ @〈a,b〉 | #c #tl'']]]
 #abs normalize in abs; destruct
qed.

axiom NotATwoBytesPointer: String.

(* Fails if the address is not representable as a pair *)
definition beval_pair_of_pointer: pointer → res (beval × beval) ≝
 λp. match p with [ mk_pointer pty pbl pok poff ⇒
  match pty with
   [ XData ⇒ λpok. OK … (list_to_pair … (bevals_of_pointer (mk_pointer XData pbl pok poff)) ?)
   | Code ⇒ λpok. OK … (list_to_pair … (bevals_of_pointer (mk_pointer Code pbl pok poff)) ?)
   | _ ⇒ λ_. Error … [MSG NotATwoBytesPointer]] pok].
% qed.

axiom ValueNotABoolean: String.

definition bool_of_beval: beval → res bool ≝
 λv.match v with
  [ BVundef ⇒ Error … [MSG ValueNotABoolean]
  | BVByte b ⇒ OK … (eq_bv … (zero …) b)
  | BVnull x y ⇒  OK … false
  | BVptr p q ⇒ OK ? true ].

axiom BadByte: String.

definition Byte_of_val: beval → res Byte ≝ (*CSC: move elsewhere *)
 λb.match b with
  [ BVByte b ⇒ OK … b
  | _ ⇒ Error … [MSG BadByte]].

(* CSC: maybe we should introduce a type of 1-bit-sized values *)
definition BVtrue: beval ≝ BVByte [[false;false;false;false;false;false;false;true]].
definition BVfalse: beval ≝ BVByte (zero …).
definition beval_of_bool : bool → beval ≝ λb. if b then BVtrue else BVfalse.