proposition: Lemma fr_general_prop: forall depth from to p g g' A (Q: LGraph -> A -> nat -> Prop) (P: LGraph -> LGraph -> A -> Prop) (R: nat -> nat -> Prop), R from to -> graph_has_gen g to -> (forall g v, P g g v) -> (forall g1 g2 g3 v, P g1 g2 v -> P g2 g3 v -> P g1 g3 v) -> (forall g e v x, P g (labeledgraph_gen_dst g e v) x) -> (forall from g v to x, graph_has_gen g to -> Q g x from -> (vlabel g v).(raw_mark) = false -> R from to -> vgeneration v = from -> P g (lgraph_copy_v g v to) x) -> (forall depth from to p g g', graph_has_gen g to -> forward_relation from to depth p g g' -> forall v, Q g v from -> Q g' v from) -> (forall g v to x from, graph_has_gen g to -> Q g x from -> Q (lgraph_copy_v g v to) x from) -> (forall g e v x from, Q g x from -> Q (labeledgraph_gen_dst g e v) x from) -> forward_relation from to depth p g g' -> forall v, Q g v from -> P g g' v.
proof: Proof. induction depth; intros. - inversion H8; subst; try (specialize (H1 g' v); assumption); try solve [eauto]. - assert (forall l from to g1 g2, graph_has_gen g1 to -> forward_loop from to depth l g1 g2 -> R from to -> forall v, Q g1 v from -> P g1 g2 v). { induction l; intros; inversion H11. 1: apply H1. subst. specialize (IHdepth _ _ _ _ _ _ _ _ _ H12 H10 H1 H2 H3 H4 H5 H6 H7 H17 _ H13). apply (H5 _ _ _ _ _ _ H10 H17) in H13. rewrite (fr_graph_has_gen _ _ _ _ _ _ H10 H17) in H10. specialize (IHl _ _ _ _ H10 H20 H12 _ H13). apply (H2 _ _ _ _ IHdepth IHl). } clear IHdepth. inversion H8; subst; try (specialize (H1 g' v); assumption); try solve [eauto]. + cut (P g new_g v). * intros. apply (H2 g new_g g'). 1: assumption. assert (graph_has_gen new_g to) by (subst new_g; rewrite <- lcv_graph_has_gen; assumption). apply (H10 _ _ _ _ _ H12 H15 H). subst new_g. apply H6; assumption. * subst new_g. apply (H4 (vgeneration v0)); [assumption.. | reflexivity]. + cut (P g new_g v). * intros. apply (H2 g new_g g'). 1: assumption. assert (graph_has_gen new_g to) by (subst new_g; rewrite lgd_graph_has_gen, <- lcv_graph_has_gen; assumption). apply (H10 _ _ _ _ _ H12 H15 H). subst new_g. apply H7, H6; assumption. * subst new_g. remember (lgraph_copy_v g (dst g e) to) as g1. remember (labeledgraph_gen_dst g1 e (new_copied_v g to)) as g2. cut (P g1 g2 v). 2: subst; apply H3. intros. apply (H2 g g1 g2). 2: assumption. subst g1. apply (H4 (vgeneration (dst g e))); [assumption.. | reflexivity]. Qed.
imports: Coq.ZArith.ZArith Coq.Program.Basics Coq.micromega.Lia compcert.lib.Integers compcert.common.Values VST.veric.base VST.veric.Clight_lemmas VST.veric.val_lemmas VST.veric.shares VST.msl.seplog VST.msl.shares VST.zlist.sublist VST.floyd.coqlib3 VST.floyd.functional_base VST.floyd.data_at_rec_lemmas VST.zlist.list_solver CertiGraph.lib.EquivDec_ext CertiGraph.lib.List_ext CertiGraph.graph.graph_model CertiGraph.graph.graph_gen