diff --git a/thys/Jinja/BV/BVNoTypeError.thy b/thys/Jinja/BV/BVNoTypeError.thy --- a/thys/Jinja/BV/BVNoTypeError.thy +++ b/thys/Jinja/BV/BVNoTypeError.thy @@ -1,312 +1,309 @@ (* Title: HOL/MicroJava/BV/BVNoTypeErrors.thy Author: Gerwin Klein Copyright GPL *) section \Welltyped Programs produce no Type Errors\ theory BVNoTypeError imports "../JVM/JVMDefensive" BVSpecTypeSafe begin lemma has_methodI: "P \ C sees M:Ts\T = m in D \ P \ C has M" by (unfold has_method_def) blast text \ Some simple lemmas about the type testing functions of the defensive JVM: \ lemma typeof_NoneD [simp,dest]: "typeof v = Some x \ \is_Addr v" by (cases v) auto lemma is_Ref_def2: "is_Ref v = (v = Null \ (\a. v = Addr a))" by (cases v) (auto simp add: is_Ref_def) lemma [iff]: "is_Ref Null" by (simp add: is_Ref_def2) lemma is_RefI [intro, simp]: "P,h \ v :\ T \ is_refT T \ is_Ref v" (*<*) - apply (cases T) - apply (auto simp add: is_refT_def is_Ref_def dest: conf_ClassD) - done +proof (cases T) +qed (auto simp add: is_refT_def is_Ref_def dest: conf_ClassD) (*>*) lemma is_IntgI [intro, simp]: "P,h \ v :\ Integer \ is_Intg v" -(*<*) - apply (unfold conf_def) - apply auto - done -(*>*) +(*<*)by (unfold conf_def) auto(*>*) lemma is_BoolI [intro, simp]: "P,h \ v :\ Boolean \ is_Bool v" -(*<*) - apply (unfold conf_def) - apply auto - done -(*>*) +(*<*)by (unfold conf_def) auto(*>*) declare defs1 [simp del] lemma wt_jvm_prog_states: - "\ wf_jvm_prog\<^bsub>\\<^esub> P; P \ C sees M: Ts\T = (mxs, mxl, ins, et) in C; - \ C M ! pc = \; pc < size ins \ - \ OK \ \ states P mxs (1+size Ts+mxl)" +assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" + and mC: "P \ C sees M: Ts\T = (mxs, mxl, ins, et) in C" + and \: "\ C M ! pc = \" and pc: "pc < size ins" +shows "OK \ \ states P mxs (1+size Ts+mxl)" (*<*) - apply (unfold wf_jvm_prog_phi_def) - apply (drule (1) sees_wf_mdecl) - apply (simp add: wf_mdecl_def wt_method_def check_types_def) - apply (blast intro: nth_in) - done +proof - + let ?wf_md = "(\P C (M, Ts, T\<^sub>r, mxs, mxl\<^sub>0, is, xt). + wt_method P C Ts T\<^sub>r mxs mxl\<^sub>0 is xt (\ C M))" + have wfmd: "wf_prog ?wf_md P" using wf + by (unfold wf_jvm_prog_phi_def) assumption + show ?thesis using sees_wf_mdecl[OF wfmd mC] \ pc + by (simp add: wf_mdecl_def wt_method_def check_types_def) + (blast intro: nth_in) +qed (*>*) text \ The main theorem: welltyped programs do not produce type errors if they are started in a conformant state. \ theorem no_type_error: fixes \ :: jvm_state assumes welltyped: "wf_jvm_prog\<^bsub>\\<^esub> P" and conforms: "P,\ \ \ \" shows "exec_d P \ \ TypeError" (*<*) proof - from welltyped obtain mb where wf: "wf_prog mb P" by (fast dest: wt_jvm_progD) obtain xcp h frs where s [simp]: "\ = (xcp, h, frs)" by (cases \) from conforms have "xcp \ None \ frs = [] \ check P \" by (unfold correct_state_def check_def) auto moreover { assume "\(xcp \ None \ frs = [])" then obtain stk reg C M pc frs' where xcp [simp]: "xcp = None" and frs [simp]: "frs = (stk,reg,C,M,pc)#frs'" by (clarsimp simp add: neq_Nil_conv) from conforms obtain ST LT Ts T mxs mxl ins xt where hconf: "P \ h \" and meth: "P \ C sees M:Ts\T = (mxs, mxl, ins, xt) in C" and \: "\ C M ! pc = Some (ST,LT)" and frame: "conf_f P h (ST,LT) ins (stk,reg,C,M,pc)" and frames: "conf_fs P h \ M (size Ts) T frs'" by (fastforce simp add: correct_state_def dest: sees_method_fun) from frame obtain stk: "P,h \ stk [:\] ST" and reg: "P,h \ reg [:\\<^sub>\] LT" and pc: "pc < size ins" by (simp add: conf_f_def) from welltyped meth \ pc have "OK (Some (ST, LT)) \ states P mxs (1+size Ts+mxl)" by (rule wt_jvm_prog_states) hence "size ST \ mxs" by (auto simp add: JVM_states_unfold) with stk have mxs: "size stk \ mxs" by (auto dest: list_all2_lengthD) from welltyped meth pc have "P,T,mxs,size ins,xt \ ins!pc,pc :: \ C M" by (rule wt_jvm_prog_impl_wt_instr) hence app\<^sub>0: "app (ins!pc) P mxs T pc (size ins) xt (\ C M!pc) " by (simp add: wt_instr_def) with \ have eff: "\(pc',s')\set (eff (ins ! pc) P pc xt (\ C M ! pc)). pc' < size ins" by (unfold app_def) simp from app\<^sub>0 \ have app: "xcpt_app (ins!pc) P pc mxs xt (ST,LT) \ app\<^sub>i (ins!pc, P, pc, mxs, T, (ST,LT))" by (clarsimp simp add: app_def) with eff stk reg have "check_instr (ins!pc) P h stk reg C M pc frs'" proof (cases "ins!pc") case (Getfield F C) with app stk reg \ obtain v vT stk' where field: "P \ C sees F:vT in C" and stk: "stk = v # stk'" and conf: "P,h \ v :\ Class C" by auto from conf have is_Ref: "is_Ref v" by auto moreover { assume "v \ Null" with conf field is_Ref wf have "\D vs. h (the_Addr v) = Some (D,vs) \ P \ D \\<^sup>* C" by (auto dest!: non_npD) } - ultimately show ?thesis using Getfield field stk hconf - apply clarsimp - apply (rule conjI, fastforce) - apply clarsimp - apply (drule has_visible_field) - apply (drule (1) has_field_mono) - apply (drule (1) hconfD) - apply (unfold oconf_def has_field_def) - apply clarsimp - apply (fastforce dest: has_fields_fun) - done + ultimately show ?thesis using Getfield field stk + has_field_mono[OF has_visible_field[OF field]] hconfD[OF hconf] + by (unfold oconf_def has_field_def) (fastforce dest: has_fields_fun) next case (Putfield F C) with app stk reg \ obtain v ref vT stk' where field: "P \ C sees F:vT in C" and stk: "stk = v # ref # stk'" and confv: "P,h \ v :\ vT" and confr: "P,h \ ref :\ Class C" by fastforce from confr have is_Ref: "is_Ref ref" by simp moreover { assume "ref \ Null" with confr field is_Ref wf have "\D vs. h (the_Addr ref) = Some (D,vs) \ P \ D \\<^sup>* C" by (auto dest: non_npD) } ultimately show ?thesis using Putfield field stk confv by fastforce next case (Invoke M' n) with app have n: "n < size ST" by simp from stk have [simp]: "size stk = size ST" by (rule list_all2_lengthD) { assume "stk!n = Null" with n Invoke have ?thesis by simp } moreover { assume "ST!n = NT" with n stk have "stk!n = Null" by (auto simp: list_all2_conv_all_nth) with n Invoke have ?thesis by simp } moreover { assume Null: "stk!n \ Null" and NT: "ST!n \ NT" from NT app Invoke obtain D D' Ts T m where D: "ST!n = Class D" and M': "P \ D sees M': Ts\T = m in D'" and Ts: "P \ rev (take n ST) [\] Ts" by auto from D stk n have "P,h \ stk!n :\ Class D" by (auto simp: list_all2_conv_all_nth) with Null obtain a C' fs where [simp]: "stk!n = Addr a" "h a = Some (C',fs)" and "P \ C' \\<^sup>* D" by (fastforce dest!: conf_ClassD) with M' wf obtain m' Ts' T' D'' where C': "P \ C' sees M': Ts'\T' = m' in D''" and Ts': "P \ Ts [\] Ts'" by (auto dest!: sees_method_mono) from stk have "P,h \ take n stk [:\] take n ST" .. hence "P,h \ rev (take n stk) [:\] rev (take n ST)" .. also note Ts also note Ts' finally have "P,h \ rev (take n stk) [:\] Ts'" . with Invoke Null n C' have ?thesis by (auto simp add: is_Ref_def2 has_methodI) } ultimately show ?thesis by blast next case Return with stk app \ meth frames show ?thesis by (auto simp add: has_methodI) qed (auto simp add: list_all2_lengthD) hence "check P \" using meth pc mxs by (simp add: check_def has_methodI) } ultimately have "check P \" by blast thus "exec_d P \ \ TypeError" .. qed (*>*) text \ The theorem above tells us that, in welltyped programs, the defensive machine reaches the same result as the aggressive one (after arbitrarily many steps). \ theorem welltyped_aggressive_imp_defensive: "wf_jvm_prog\<^bsub>\\<^esub> P \ P,\ \ \ \ \ P \ \ -jvm\ \' \ P \ (Normal \) -jvmd\ (Normal \')" (*<*) - apply (simp only: exec_all_def) - apply (erule rtrancl_induct) - apply (simp add: exec_all_d_def1) - apply simp - apply (simp only: exec_all_def [symmetric]) - apply (frule BV_correct, assumption+) - apply (drule no_type_error, assumption, drule no_type_error_commutes, simp) - apply (simp add: exec_all_d_def1) - apply (rule rtrancl_trans, assumption) - apply (drule exec_1_d_NormalI) - apply auto - done +proof - + assume wf: "wf_jvm_prog\<^bsub>\\<^esub> P" and cf: "P,\ \ \ \" and exec: "P \ \ -jvm\ \'" + then have "(\, \') \ {(\, \'). exec (P, \) = \\'\}\<^sup>*" by(simp only: exec_all_def) + then show ?thesis proof(induct rule: rtrancl_induct) + case base + then show ?case by (simp add: exec_all_d_def1) + next + case (step y z) + then have \y: "P \ \ -jvm\ y" by (simp only: exec_all_def [symmetric]) + have exec_d: "exec_d P y = Normal \z\" using step + no_type_error_commutes[OF no_type_error[OF wf BV_correct[OF wf \y cf]]] + by (simp add: exec_all_d_def1) + show ?case using step.hyps(3) exec_1_d_NormalI[OF exec_d] + by (simp add: exec_all_d_def1) + qed +qed (*>*) text \ As corollary we get that the aggressive and the defensive machine are equivalent for welltyped programs (if started in a conformant state or in the canonical start state) \ corollary welltyped_commutes: fixes \ :: jvm_state assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" and conforms: "P,\ \ \ \" shows "P \ (Normal \) -jvmd\ (Normal \') = P \ \ -jvm\ \'" - apply rule - apply (erule defensive_imp_aggressive) - apply (erule welltyped_aggressive_imp_defensive [OF wf conforms]) - done +proof(rule iffI) + assume "P \ Normal \ -jvmd\ Normal \'" then show "P \ \ -jvm\ \'" + by (rule defensive_imp_aggressive) +next + assume "P \ \ -jvm\ \'" then show "P \ Normal \ -jvmd\ Normal \'" + by (rule welltyped_aggressive_imp_defensive [OF wf conforms]) +qed corollary welltyped_initial_commutes: assumes wf: "wf_jvm_prog P" assumes meth: "P \ C sees M:[]\T = b in C" defines start: "\ \ start_state P C M" shows "P \ (Normal \) -jvmd\ (Normal \') = P \ \ -jvm\ \'" proof - from wf obtain \ where wf': "wf_jvm_prog\<^bsub>\\<^esub> P" by (auto simp: wf_jvm_prog_def) from this meth have "P,\ \ \ \" unfolding start by (rule BV_correct_initial) with wf' show ?thesis by (rule welltyped_commutes) qed lemma not_TypeError_eq [iff]: "x \ TypeError = (\t. x = Normal t)" by (cases x) auto locale cnf = fixes P and \ and \ assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" assumes cnf: "correct_state P \ \" theorem (in cnf) no_type_errors: "P \ (Normal \) -jvmd\ \' \ \' \ TypeError" - apply (unfold exec_all_d_def1) - apply (erule rtrancl_induct) - apply simp - apply (fold exec_all_d_def1) - apply (insert cnf wf) - apply clarsimp - apply (drule defensive_imp_aggressive) - apply (frule (2) BV_correct) - apply (drule (1) no_type_error) back - apply (auto simp add: exec_1_d_eq) - done +proof - + assume "P \ (Normal \) -jvmd\ \'" + then have "(Normal \, \') \ (exec_1_d P)\<^sup>*" by (unfold exec_all_d_def1) simp + then show ?thesis proof(induct rule: rtrancl_induct) + case (step y z) + then obtain y\<^sub>n where [simp]: "y = Normal y\<^sub>n" by clarsimp + have n\y: "P \ Normal \ -jvmd\ Normal y\<^sub>n" using step.hyps(1) + by (fold exec_all_d_def1) simp + have \y: "P \ \ -jvm\ y\<^sub>n" using defensive_imp_aggressive[OF n\y] by simp + show ?case using step no_type_error[OF wf BV_correct[OF wf \y cnf]] + by (auto simp add: exec_1_d_eq) + qed simp +qed locale start = fixes P and C and M and \ and T and b assumes wf: "wf_jvm_prog P" assumes sees: "P \ C sees M:[]\T = b in C" defines "\ \ Normal (start_state P C M)" corollary (in start) bv_no_type_error: shows "P \ \ -jvmd\ \' \ \' \ TypeError" proof - from wf obtain \ where "wf_jvm_prog\<^bsub>\\<^esub> P" by (auto simp: wf_jvm_prog_def) moreover with sees have "correct_state P \ (start_state P C M)" by - (rule BV_correct_initial) ultimately have "cnf P \ (start_state P C M)" by (rule cnf.intro) moreover assume "P \ \ -jvmd\ \'" ultimately show ?thesis by (unfold \_def) (rule cnf.no_type_errors) qed end diff --git a/thys/JinjaDCI/BV/BVNoTypeError.thy b/thys/JinjaDCI/BV/BVNoTypeError.thy --- a/thys/JinjaDCI/BV/BVNoTypeError.thy +++ b/thys/JinjaDCI/BV/BVNoTypeError.thy @@ -1,394 +1,389 @@ (* Title: JinjaDCI/BV/BVNoTypeErrors.thy Author: Gerwin Klein, Susannah Mansky Copyright GPL Based on the Jinja theory BV/BVNoTypeErrors.thy by Gerwin Klein *) section \ Welltyped Programs produce no Type Errors \ theory BVNoTypeError imports "../JVM/JVMDefensive" BVSpecTypeSafe begin lemma has_methodI: "P \ C sees M,b:Ts\T = m in D \ P \ C has M,b" by (unfold has_method_def) blast text \ Some simple lemmas about the type testing functions of the defensive JVM: \ lemma typeof_NoneD [simp,dest]: "typeof v = Some x \ \is_Addr v" by (cases v) auto lemma is_Ref_def2: "is_Ref v = (v = Null \ (\a. v = Addr a))" by (cases v) (auto simp add: is_Ref_def) lemma [iff]: "is_Ref Null" by (simp add: is_Ref_def2) lemma is_RefI [intro, simp]: "P,h \ v :\ T \ is_refT T \ is_Ref v" (*<*) - apply (cases T) - apply (auto simp add: is_refT_def is_Ref_def dest: conf_ClassD) - done +proof(cases T) +qed (auto simp add: is_refT_def is_Ref_def dest: conf_ClassD) (*>*) lemma is_IntgI [intro, simp]: "P,h \ v :\ Integer \ is_Intg v" -(*<*) - apply (unfold conf_def) - apply auto - done -(*>*) +(*<*)by (unfold conf_def) auto(*>*) lemma is_BoolI [intro, simp]: "P,h \ v :\ Boolean \ is_Bool v" -(*<*) - apply (unfold conf_def) - apply auto - done -(*>*) +(*<*)by (unfold conf_def) auto(*>*) declare defs1 [simp del] lemma wt_jvm_prog_states_NonStatic: - "\ wf_jvm_prog\<^bsub>\\<^esub> P; P \ C sees M,NonStatic: Ts\T = (mxs, mxl, ins, et) in C; - \ C M ! pc = \; pc < size ins \ - \ OK \ \ states P mxs (1+size Ts+mxl)" +assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" + and mC: "P \ C sees M,NonStatic: Ts\T = (mxs, mxl, ins, et) in C" + and \: "\ C M ! pc = \" and pc: "pc < size ins" +shows "OK \ \ states P mxs (1+size Ts+mxl)" (*<*) - apply (unfold wf_jvm_prog_phi_def) - apply (drule (1) sees_wf_mdecl) - apply (simp add: wf_mdecl_def wt_method_def check_types_def) - apply (blast intro: nth_in) - done +proof - + let ?wf_md = "(\P C (M, b, Ts, T\<^sub>r, mxs, mxl\<^sub>0, is, xt). + wt_method P C b Ts T\<^sub>r mxs mxl\<^sub>0 is xt (\ C M))" + have wfmd: "wf_prog ?wf_md P" using wf + by (unfold wf_jvm_prog_phi_def) assumption + show ?thesis using sees_wf_mdecl[OF wfmd mC] \ pc + by (simp add: wf_mdecl_def wt_method_def check_types_def) + (blast intro: nth_in) +qed (*>*) lemma wt_jvm_prog_states_Static: - "\ wf_jvm_prog\<^bsub>\\<^esub> P; P \ C sees M,Static: Ts\T = (mxs, mxl, ins, et) in C; - \ C M ! pc = \; pc < size ins \ - \ OK \ \ states P mxs (size Ts+mxl)" +assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" + and mC: "P \ C sees M,Static: Ts\T = (mxs, mxl, ins, et) in C" + and \: "\ C M ! pc = \" and pc: "pc < size ins" +shows "OK \ \ states P mxs (size Ts+mxl)" (*<*) - apply (unfold wf_jvm_prog_phi_def) - apply (drule (1) sees_wf_mdecl) - apply (simp add: wf_mdecl_def wt_method_def check_types_def) - apply (blast intro: nth_in) - done +proof - + let ?wf_md = "(\P C (M, b, Ts, T\<^sub>r, mxs, mxl\<^sub>0, is, xt). + wt_method P C b Ts T\<^sub>r mxs mxl\<^sub>0 is xt (\ C M))" + have wfmd: "wf_prog ?wf_md P" using wf + by (unfold wf_jvm_prog_phi_def) assumption + show ?thesis using sees_wf_mdecl[OF wfmd mC] \ pc + by (simp add: wf_mdecl_def wt_method_def check_types_def) + (blast intro: nth_in) +qed (*>*) text \ The main theorem: welltyped programs do not produce type errors if they are started in a conformant state. \ theorem no_type_error: fixes \ :: jvm_state assumes welltyped: "wf_jvm_prog\<^bsub>\\<^esub> P" and conforms: "P,\ \ \ \" shows "exec_d P \ \ TypeError" (*<*) proof - from welltyped obtain mb where wf: "wf_prog mb P" by (fast dest: wt_jvm_progD) obtain xcp h frs sh where s [simp]: "\ = (xcp, h, frs, sh)" by (cases \) from conforms have "xcp \ None \ frs = [] \ check P \" by (unfold correct_state_def check_def) auto moreover { assume "\(xcp \ None \ frs = [])" then obtain stk reg C M pc ics frs' where xcp [simp]: "xcp = None" and frs [simp]: "frs = (stk,reg,C,M,pc,ics)#frs'" by (clarsimp simp add: neq_Nil_conv) from conforms obtain ST LT b Ts T mxs mxl ins xt where hconf: "P \ h \" and shconf: "P,h \\<^sub>s sh \" and meth: "P \ C sees M,b:Ts\T = (mxs, mxl, ins, xt) in C" and \: "\ C M ! pc = Some (ST,LT)" and frame: "conf_f P h sh (ST,LT) ins (stk,reg,C,M,pc,ics)" and frames: "conf_fs P h sh \ C M (size Ts) T frs'" by (fastforce simp add: correct_state_def dest: sees_method_fun) from frame obtain stk: "P,h \ stk [:\] ST" and reg: "P,h \ reg [:\\<^sub>\] LT" and pc: "pc < size ins" by (simp add: conf_f_def) from welltyped meth \ pc have "OK (Some (ST, LT)) \ states P mxs (1+size Ts+mxl) \ OK (Some (ST, LT)) \ states P mxs (size Ts+mxl)" by (cases b, auto dest: wt_jvm_prog_states_NonStatic wt_jvm_prog_states_Static) hence "size ST \ mxs" by (auto simp add: JVM_states_unfold) with stk have mxs: "size stk \ mxs" by (auto dest: list_all2_lengthD) from welltyped meth pc have "P,T,mxs,size ins,xt \ ins!pc,pc :: \ C M" by (rule wt_jvm_prog_impl_wt_instr) hence app\<^sub>0: "app (ins!pc) P mxs T pc (size ins) xt (\ C M!pc) " by (simp add: wt_instr_def) with \ have eff: "\(pc',s')\set (eff (ins ! pc) P pc xt (\ C M ! pc)). pc' < size ins" by (unfold app_def) simp from app\<^sub>0 \ have app: "xcpt_app (ins!pc) P pc mxs xt (ST,LT) \ app\<^sub>i (ins!pc, P, pc, mxs, T, (ST,LT))" by (clarsimp simp add: app_def) with eff stk reg have "check_instr (ins!pc) P h stk reg C M pc frs' sh" proof (cases "ins!pc") case (Getfield F C) with app stk reg \ obtain v vT stk' where field: "P \ C sees F,NonStatic:vT in C" and stk: "stk = v # stk'" and conf: "P,h \ v :\ Class C" by auto from conf have is_Ref: "is_Ref v" by auto moreover { assume "v \ Null" with conf field is_Ref wf have "\D vs. h (the_Addr v) = Some (D,vs) \ P \ D \\<^sup>* C" by (auto dest!: non_npD) } - ultimately show ?thesis using Getfield field stk hconf - apply clarsimp - apply (rule conjI, fastforce) - apply clarsimp - apply (drule has_visible_field) - apply (drule (1) has_field_mono) - apply (drule (1) hconfD) - apply (unfold oconf_def has_field_def) - apply clarsimp - apply (fastforce dest: has_fields_fun) - done + ultimately show ?thesis using Getfield field stk + has_field_mono[OF has_visible_field[OF field]] hconfD[OF hconf] + by (unfold oconf_def has_field_def) (fastforce dest: has_fields_fun) next case (Getstatic C F D) with app stk reg \ obtain vT where field: "P \ C sees F,Static:vT in D" by auto - then show ?thesis using Getstatic field stk shconf - apply clarsimp - apply (rule conjI, fastforce) - apply clarsimp - apply (drule has_visible_field) - apply (drule has_field_idemp) - apply (drule (1) shconfD) - apply (unfold soconf_def has_field_def) - apply clarsimp - apply (fastforce dest: has_fields_fun) - done + then show ?thesis using Getstatic stk + has_field_idemp[OF has_visible_field[OF field]] shconfD[OF shconf] + by (unfold soconf_def has_field_def) (fastforce dest: has_fields_fun) next case (Putfield F C) with app stk reg \ obtain v ref vT stk' where field: "P \ C sees F,NonStatic:vT in C" and stk: "stk = v # ref # stk'" and confv: "P,h \ v :\ vT" and confr: "P,h \ ref :\ Class C" by fastforce from confr have is_Ref: "is_Ref ref" by simp moreover { assume "ref \ Null" with confr field is_Ref wf have "\D vs. h (the_Addr ref) = Some (D,vs) \ P \ D \\<^sup>* C" by (auto dest: non_npD) } ultimately show ?thesis using Putfield field stk confv by fastforce next case (Invoke M' n) with app have n: "n < size ST" by simp from stk have [simp]: "size stk = size ST" by (rule list_all2_lengthD) { assume "stk!n = Null" with n Invoke have ?thesis by simp } moreover { assume "ST!n = NT" with n stk have "stk!n = Null" by (auto simp: list_all2_conv_all_nth) with n Invoke have ?thesis by simp } moreover { assume Null: "stk!n \ Null" and NT: "ST!n \ NT" from NT app Invoke obtain D D' Ts T m where D: "ST!n = Class D" and M': "P \ D sees M',NonStatic: Ts\T = m in D'" and Ts: "P \ rev (take n ST) [\] Ts" by auto from D stk n have "P,h \ stk!n :\ Class D" by (auto simp: list_all2_conv_all_nth) with Null obtain a C' fs where [simp]: "stk!n = Addr a" "h a = Some (C',fs)" and "P \ C' \\<^sup>* D" by (fastforce dest!: conf_ClassD) with M' wf obtain m' Ts' T' D'' where C': "P \ C' sees M',NonStatic: Ts'\T' = m' in D''" and Ts': "P \ Ts [\] Ts'" by (auto dest!: sees_method_mono) from stk have "P,h \ take n stk [:\] take n ST" .. hence "P,h \ rev (take n stk) [:\] rev (take n ST)" .. also note Ts also note Ts' finally have "P,h \ rev (take n stk) [:\] Ts'" . with Invoke Null n C' have ?thesis by (auto simp add: is_Ref_def2 has_methodI) } ultimately show ?thesis by blast next case (Invokestatic C M' n) with app have n: "n \ size ST" by simp from stk have [simp]: "size stk = size ST" by (rule list_all2_lengthD) from app Invokestatic obtain D Ts T m where M': "P \ C sees M',Static: Ts\T = m in D" and Ts: "P \ rev (take n ST) [\] Ts" by auto from stk have "P,h \ take n stk [:\] take n ST" .. hence "P,h \ rev (take n stk) [:\] rev (take n ST)" .. also note Ts finally have "P,h \ rev (take n stk) [:\] Ts" . with Invokestatic n M' show ?thesis by (auto simp add: is_Ref_def2 has_methodI) next case Return show ?thesis proof(cases "M = clinit") case True have "is_class P C" by(rule sees_method_is_class[OF meth]) with wf_sees_clinit[OF wf] obtain m where "P \ C sees clinit,Static: [] \ Void = m in C" by(fastforce simp: is_class_def) with stk app \ meth frames True Return show ?thesis by (auto simp add: has_methodI) next case False with stk app \ meth frames Return show ?thesis by (auto intro: has_methodI) qed qed (auto simp add: list_all2_lengthD) hence "check P \" using meth pc mxs by (auto simp: check_def intro: has_methodI) } ultimately have "check P \" by blast thus "exec_d P \ \ TypeError" .. qed (*>*) text \ The theorem above tells us that, in welltyped programs, the defensive machine reaches the same result as the aggressive one (after arbitrarily many steps). \ theorem welltyped_aggressive_imp_defensive: "wf_jvm_prog\<^bsub>\\<^esub> P \ P,\ \ \ \ \ P \ \ -jvm\ \' \ P \ (Normal \) -jvmd\ (Normal \')" (*<*) - apply (simp only: exec_all_def) - apply (erule rtrancl_induct) - apply (simp add: exec_all_d_def1) - apply simp - apply (simp only: exec_all_def [symmetric]) - apply (frule BV_correct, assumption+) - apply (drule no_type_error, assumption, drule no_type_error_commutes, simp) - apply (simp add: exec_all_d_def1) - apply (rule rtrancl_trans, assumption) - apply (drule exec_1_d_NormalI) - apply auto - done +proof - + assume wf: "wf_jvm_prog\<^bsub>\\<^esub> P" and cf: "P,\ \ \ \" and exec: "P \ \ -jvm\ \'" + then have "(\, \') \ {(\, \'). exec (P, \) = \\'\}\<^sup>*" by(simp only: exec_all_def) + then show ?thesis proof(induct rule: rtrancl_induct) + case base + then show ?case by (simp add: exec_all_d_def1) + next + case (step y z) + then have \y: "P \ \ -jvm\ y" by (simp only: exec_all_def [symmetric]) + have exec_d: "exec_d P y = Normal \z\" using step + no_type_error_commutes[OF no_type_error[OF wf BV_correct[OF wf \y cf]]] + by (simp add: exec_all_d_def1) + show ?case using step.hyps(3) exec_1_d_NormalI[OF exec_d] + by (simp add: exec_all_d_def1) + qed +qed (*>*) text \ As corollary we get that the aggressive and the defensive machine are equivalent for welltyped programs (if started in a conformant state or in the canonical start state) \ corollary welltyped_commutes: fixes \ :: jvm_state assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" and conforms: "P,\ \ \ \" shows "P \ (Normal \) -jvmd\ (Normal \') = P \ \ -jvm\ \'" - apply rule - apply (erule defensive_imp_aggressive) - apply (erule welltyped_aggressive_imp_defensive [OF wf conforms]) - done +proof(rule iffI) + assume "P \ Normal \ -jvmd\ Normal \'" then show "P \ \ -jvm\ \'" + by (rule defensive_imp_aggressive) +next + assume "P \ \ -jvm\ \'" then show "P \ Normal \ -jvmd\ Normal \'" + by (rule welltyped_aggressive_imp_defensive [OF wf conforms]) +qed corollary welltyped_initial_commutes: assumes wf: "wf_jvm_prog P" assumes nstart: "\ is_class P Start" assumes meth: "P \ C sees M,Static:[]\Void = b in C" assumes nclinit: "M \ clinit" assumes Obj_start_m: "(\b' Ts' T' m' D'. P \ Object sees start_m, b' : Ts'\T' = m' in D' \ b' = Static \ Ts' = [] \ T' = Void)" defines start: "\ \ start_state P" shows "start_prog P C M \ (Normal \) -jvmd\ (Normal \') = start_prog P C M \ \ -jvm\ \'" proof - from wf obtain \ where wf': "wf_jvm_prog\<^bsub>\\<^esub> P" by (auto simp: wf_jvm_prog_def) let ?\ = "\_start \" from start_prog_wf_jvm_prog_phi[where \'="?\", OF wf' nstart meth nclinit \_start Obj_start_m] have "wf_jvm_prog\<^bsub>?\\<^esub>(start_prog P C M)" by simp moreover from wf' nstart meth nclinit \_start(2) have "start_prog P C M,?\ \ \ \" unfolding start by (rule BV_correct_initial) ultimately show ?thesis by (rule welltyped_commutes) qed lemma not_TypeError_eq [iff]: "x \ TypeError = (\t. x = Normal t)" by (cases x) auto locale cnf = fixes P and \ and \ assumes wf: "wf_jvm_prog\<^bsub>\\<^esub> P" assumes cnf: "correct_state P \ \" theorem (in cnf) no_type_errors: "P \ (Normal \) -jvmd\ \' \ \' \ TypeError" - apply (unfold exec_all_d_def1) - apply (erule rtrancl_induct) - apply simp - apply (fold exec_all_d_def1) - apply (insert cnf wf) - apply clarsimp - apply (drule defensive_imp_aggressive) - apply (frule (2) BV_correct) - apply (auto simp add: exec_1_d_eq dest: no_type_error) - done +proof - + assume "P \ (Normal \) -jvmd\ \'" + then have "(Normal \, \') \ (exec_1_d P)\<^sup>*" by (unfold exec_all_d_def1) simp + then show ?thesis proof(induct rule: rtrancl_induct) + case (step y z) + then obtain y\<^sub>n where [simp]: "y = Normal y\<^sub>n" by clarsimp + have n\y: "P \ Normal \ -jvmd\ Normal y\<^sub>n" using step.hyps(1) + by (fold exec_all_d_def1) simp + have \y: "P \ \ -jvm\ y\<^sub>n" using defensive_imp_aggressive[OF n\y] by simp + show ?case using step no_type_error[OF wf BV_correct[OF wf \y cnf]] + by (auto simp add: exec_1_d_eq) + qed simp +qed locale start = fixes P and C and M and \ and T and b and P\<^sub>0 assumes wf: "wf_jvm_prog P" assumes nstart: "\ is_class P Start" assumes sees: "P \ C sees M,Static:[]\Void = b in C" assumes nclinit: "M \ clinit" assumes Obj_start_m: "(\b' Ts' T' m' D'. P \ Object sees start_m, b' : Ts'\T' = m' in D' \ b' = Static \ Ts' = [] \ T' = Void)" defines "\ \ Normal (start_state P)" defines [simp]: "P\<^sub>0 \ start_prog P C M" corollary (in start) bv_no_type_error: shows "P\<^sub>0 \ \ -jvmd\ \' \ \' \ TypeError" proof - from wf obtain \ where wf': "wf_jvm_prog\<^bsub>\\<^esub> P" by (auto simp: wf_jvm_prog_def) let ?\ = "\_start \" from start_prog_wf_jvm_prog_phi[where \'="?\", OF wf' nstart sees nclinit \_start Obj_start_m] have "wf_jvm_prog\<^bsub>?\\<^esub>P\<^sub>0" by simp moreover from BV_correct_initial[where \'="?\", OF wf' nstart sees nclinit \_start(2)] have "correct_state P\<^sub>0 ?\ (start_state P)" by simp ultimately have "cnf P\<^sub>0 ?\ (start_state P)" by (rule cnf.intro) moreover assume "P\<^sub>0 \ \ -jvmd\ \'" ultimately show ?thesis by (unfold \_def) (rule cnf.no_type_errors) qed end