source: src/Clight/CexecInd.ma @ 2408

include "Clight/Csyntax.ma".

(* We define a special induction principle for Clight expressions that matches
   their execution. *)

definition is_not_lvalue: expr_descr → Prop ≝
λe. match e with [ Evar _ ⇒ False | Ederef _ ⇒ False | Efield _ _ ⇒ False | _ ⇒ True ].

definition Plvalue ≝ λP:(expr → Prop).λe,ty.
match e return λ_.Prop with [ Evar _ ⇒ P (Expr e ty) | Ederef _ ⇒ P (Expr e ty) | Efield _ _ ⇒ P (Expr e ty) | _ ⇒ True ].

let rec expr_lvalue_ind
  (P:expr → Prop)
  (Q:expr_descr → type → Prop)
  (ci:∀sz,ty,i.P (Expr (Econst_int sz i) ty))
  (cf:∀ty,f.P (Expr (Econst_float f) ty))
  (lv:∀e,ty. Q e ty → Plvalue P e ty)
  (vr:∀v,ty.Q (Evar v) ty)
  (dr:∀e,ty.P e → Q (Ederef e) ty)
  (ao:∀ty,e,ty'.Q e ty' → P (Expr (Eaddrof (Expr e ty')) ty))
  (uo:∀ty,op,e.P e → P (Expr (Eunop op e) ty))
  (bo:∀ty,op,e1,e2.P e1 → P e2 → P (Expr (Ebinop op e1 e2) ty))
  (ca:∀ty,ty',e.P e → P (Expr (Ecast ty' e) ty))
  (cd:∀ty,e1,e2,e3.P e1 → P e2 → P e3 → P (Expr (Econdition e1 e2 e3) ty))
  (ab:∀ty,e1,e2.P e1 → P e2 → P (Expr (Eandbool e1 e2) ty))
  (ob:∀ty,e1,e2.P e1 → P e2 → P (Expr (Eorbool e1 e2) ty))
  (sz:∀ty,ty'. P (Expr (Esizeof ty') ty))
  (fl:∀ty,e,ty',i. Q e ty' → Q (Efield (Expr e ty') i) ty)
  (co:∀ty,l,e. P e → P (Expr (Ecost l e) ty))
  (xx:∀e,ty. is_not_lvalue e → Q e ty)
  (e:expr) on e : P e ≝
match e with
[ Expr e' ty ⇒
  match e' with
  [ Econst_int sz i ⇒ ci sz ty i
  | Econst_float f ⇒ cf ty f
  | Evar v ⇒ lv (Evar v) ty (vr v ty)
  | Ederef e'' ⇒ lv (Ederef e'') ty (dr e'' ty (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e''))
  | Eaddrof e'' ⇒ match e'' with [ Expr e0 ty0 ⇒ ao ty e0 ty0 (lvalue_expr_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e0 ty0) ]
  | Eunop op e'' ⇒ uo ty op e'' (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e'')
  | Ebinop op e1 e2 ⇒ bo ty op e1 e2 (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e1) (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e2)
  | Ecast ty' e'' ⇒ ca ty ty' e'' (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e'')
  | Econdition e1 e2 e3 ⇒ cd ty e1 e2 e3 (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e1) (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e2) (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e3)
  | Eandbool e1 e2 ⇒ ab ty e1 e2 (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e1) (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e2)
  | Eorbool e1 e2 ⇒ ob ty e1 e2 (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e1) (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e2)
  | Esizeof ty' ⇒ sz ty ty'
  | Efield e'' i ⇒ match e'' with [ Expr ef tyf ⇒ lv (Efield (Expr ef tyf) i) ty (fl ty ef tyf i (lvalue_expr_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx ef tyf)) ]
  | Ecost l e'' ⇒ co ty l e'' (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e'')
  ]
]
and lvalue_expr_ind
  (P:expr → Prop)
  (Q:expr_descr → type → Prop)
  (ci:∀sz,ty,i.P (Expr (Econst_int sz i) ty))
  (cf:∀ty,f.P (Expr (Econst_float f) ty))
  (lv:∀e,ty. Q e ty → Plvalue P e ty)
  (vr:∀v,ty.Q (Evar v) ty)
  (dr:∀e,ty.P e → Q (Ederef e) ty)
  (ao:∀ty,e,ty'.Q e ty' → P (Expr (Eaddrof (Expr e ty')) ty))
  (uo:∀ty,op,e.P e → P (Expr (Eunop op e) ty))
  (bo:∀ty,op,e1,e2.P e1 → P e2 → P (Expr (Ebinop op e1 e2) ty))
  (ca:∀ty,ty',e.P e → P (Expr (Ecast ty' e) ty))
  (cd:∀ty,e1,e2,e3.P e1 → P e2 → P e3 → P (Expr (Econdition e1 e2 e3) ty))
  (ab:∀ty,e1,e2.P e1 → P e2 → P (Expr (Eandbool e1 e2) ty))
  (ob:∀ty,e1,e2.P e1 → P e2 → P (Expr (Eorbool e1 e2) ty))
  (sz:∀ty,ty'. P (Expr (Esizeof ty') ty))
  (fl:∀ty,e,ty',i. Q e ty' → Q (Efield (Expr e ty') i) ty)
  (co:∀ty,l,e. P e → P (Expr (Ecost l e) ty))
  (xx:∀e,ty. is_not_lvalue e → Q e ty)
  (e:expr_descr) (ty:type) on e : Q e ty ≝
  match e return λe0. Q e0 ty with
  [ Evar v ⇒ vr v ty
  | Ederef e'' ⇒ dr e'' ty (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e'')
  | Efield e' i ⇒ match e' return λe1.Q (Efield e1 i) ty with [ Expr e'' ty'' ⇒ fl ty e'' ty'' i (lvalue_expr_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx e'' ty'') ]
  | _ ⇒ xx ? ty ?
  ]. whd; @I qed.

definition expr_lvalue_ind_combined ≝
λP,Q,ci,cf,lv,vr,dr,ao,uo,bo,ca,cd,ab,ob,sz,fl,co,xx.
conj ??
 (expr_lvalue_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx)
 (lvalue_expr_ind P Q ci cf lv vr dr ao uo bo ca cd ab ob sz fl co xx).