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).