theory GraphProof

lemma pc_Ret_Err_trace_end:
  "er \<in> {Ret, Err} \<Longrightarrow> pc er restrs tr
    \<Longrightarrow> tr \<in> exec_trace Gamma f
    \<Longrightarrow> \<exists>st g. trace_end tr = Some [(er, st, g)]" apply (clarsimp simp: pc_def visit_eqs trace_end_def dest!: trace_addr_SomeD) apply (frule_tac i=i in exec_trace_step_cases, simp add: all_exec_graph_step_cases) apply (cut_tac tr=tr and n="Suc i" in trace_None_dom_subset) apply (auto simp add: exec_trace_def)[2] apply (subst Max_eqI[rotated 2], erule domI) apply (simp add: finite_subset) apply (simp add: subset_iff less_Suc_eq_le) apply auto[1] done

(* Proof state trace *)
proof (prove)
goal (1 subgoal):
 1. \<lbrakk>er \<in> {Ret, Err}; pc er restrs tr; tr \<in> exec_trace Gamma f\<rbrakk> \<Longrightarrow> \<exists>st g. trace_end tr = Some [(er, st, g)] proof (prove)
goal (1 subgoal):
 1. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr (Max (dom tr)) = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (1 subgoal):
 1. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)]))))))))))\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr (Max (dom tr)) = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (3 subgoals):
 1. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)]))))))))))\<rbrakk> \<Longrightarrow> tr (Suc i) = None
 2. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)]))))))))))\<rbrakk> \<Longrightarrow> tr \<in> nat_trace_rel (?cont11 i st g) (?R11 i st g)
 3. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr (Max (dom tr)) = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (1 subgoal):
 1. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr (Max (dom tr)) = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (3 subgoals):
 1. \<And>i st g ga sta. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> finite (dom tr)
 2. \<And>i st g ga sta y. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}; y \<in> dom tr\<rbrakk> \<Longrightarrow> y \<le> i
 3. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr i = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (2 subgoals):
 1. \<And>i st g ga sta y. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}; y \<in> dom tr\<rbrakk> \<Longrightarrow> y \<le> i
 2. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr i = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal (1 subgoal):
 1. \<And>i st g. \<lbrakk>er = Ret \<or> er = Err; tr \<in> exec_trace Gamma f; restrs_condition tr restrs i; tr i = Some [(er, st, g)]; tr (Suc i) = None \<or> (\<exists>y. tr (Suc i) = Some y) \<and> (\<exists>x1. er = NextNode x1 \<and> (\<exists>x2. Gamma g = Some x2 \<and> (\<exists>x1a x2a x3. (\<exists>x4. x2 = GraphFunction x1a x2a x3 x4) \<and> (x3 x1 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. x3 x1 = Some x2 \<and> ((\<exists>x11 x12. x2 = node.Basic x11 x12 \<and> the (tr (Suc i)) = [(x11, upd_vars x12 st, g)]) \<or> (\<exists>x21 x22 x23. x2 = node.Cond x21 x22 x23 \<and> the (tr (Suc i)) = [(if x23 st then x21 else x22, st, g)]) \<or> (\<exists>x31 x32 x33. (\<exists>x34. x2 = node.Call x31 x32 x33 x34) \<and> (Gamma x32 = None \<and> the (tr (Suc i)) = [(Err, st, g)] \<or> (\<exists>x2. Gamma x32 = Some x2 \<and> (\<exists>x1a x2a x3 x4. x2 = GraphFunction x1a x2a x3 x4 \<and> the (tr (Suc i)) = [(NextNode x4, init_vars x1a x33 st, x32), (NextNode x1, st, g)])))))))))); dom tr \<subseteq> {..<Suc i}\<rbrakk> \<Longrightarrow> ((\<exists>n. tr n = None) \<longrightarrow> (\<exists>st g. tr i = Some [(er, st, g)])) \<and> (\<exists>n. tr n = None) proof (prove)
goal:
No subgoals!