proposition: Lemma labeledgraph_add_edge_ecopy1_right: forall (g g1 g2 g3 g4: Graph) (g1' g2' g3' g4': LGraph) (x l r x0 r0: addr), vvalid g x -> vgamma g x = (null, l, r) -> vcopy1 x g g1 g1' -> extended_copy l (g1: LGraph, g1') (g2: LGraph, g2') -> ecopy1 (x, L) (g2: LGraph, g2') (g3: LGraph, g3') -> extended_copy r (g3: LGraph, g3') (g4: LGraph, g4') -> x0 = LocalGraphCopy.vmap g1 x -> (x0, L) = LocalGraphCopy.emap g3 (x, L) -> r = null /\ r0 = null \/ r0 = LocalGraphCopy.vmap g4 r -> is_guarded_BinMaFin' (fun v => x0 <> v) (fun e => ~ In e ((x0, L) :: nil)) g4' -> x0 <> null -> let g5 := Graph_egen g4 (x, R) (x0, R): Graph in let g5' := labeledgraph_add_edge g4' (x0, R) x0 r0 (null, L): LGraph in ecopy1 (x, R) (g4: LGraph, g4') (g5: LGraph, g5') /\ is_guarded_BinMaFin' (fun v => x0 <> v) (fun e => ~ In e ((x0, L) :: (x0, R) :: nil)) g5' /\ (x0, R) = LocalGraphCopy.emap g5 (x, R) /\ dst g5' (x0, R) = r0.
proof: Proof. intros. unfold ecopy1. assert (~ evalid g4' (x0, R)) as HH. 1: { eapply is_BinMaFin_not_evalid; eauto. + eapply extended_copy_vvalid_mono in H4; [exact H4 |]. eapply ecopy1_vvalid_mono in H3; [exact H3 |]. eapply extended_copy_vvalid_mono in H2; [exact H2 |]. eapply vcopy1_copied_root_valid in H1; auto. subst x0; auto. + intros ? [? | []]. subst e; auto. + intros [? | []]. inversion H10. } split; [split; [| split] | split; [| split]]. + reflexivity. + apply WeakMarkGraph.labeledgraph_egen_do_nothing. + assert (g ~=~ g4) as HH0. 1: { destruct H1 as [? _], H2 as [? _], H3 as [? _], H4 as [? _]. rewrite <- H4, <- H3, <- H2, <- H1; reflexivity. } assert (x0 = LocalGraphCopy.vmap g4 (src g4 (x, R))) as HH1. 1: { rewrite left_right_sound by (rewrite <- (proj1 HH0); auto). subst x0. assert (WeakMarkGraph.marked g1 x). 1: { destruct H1 as [_ [? _]]. destruct H1 as [_ [? _]]; auto. } assert (WeakMarkGraph.marked g3 x). 1: { destruct H3 as [_ [? _]]. rewrite <- (proj2 H3). eapply WeakMarkGraph.mark_marked; [destruct H2 as [_ [H2 _]]; exact H2 | auto]. } rewrite (extended_copy_vmap_root g1 g2 g1' g2' l x) by auto. rewrite (ecopy1_vmap_root g2 g3 g2' g3' (x, L) x H3). rewrite (extended_copy_vmap_root g3 g4 g3' g4' r x) by auto. reflexivity. } destruct H7. - pose proof LocalGraphCopy.labeledgraph_egen_ecopy1_not_vvalid g4 g4' (x, R) (x0, R) x0 r0. apply H10; clear H10; auto. * destruct H7. subst r0. destruct H8 as [[? ? ?] _]. pose proof @valid_not_null' _ _ _ _ (gpredicate_sub_labeledgraph (fun v : addr => x0 <> v) (fun e : addr * LR => ~ In e ((x0, L) :: nil)) g4') _ ma' null. intro. apply H8; [| reflexivity]. simpl. rewrite Intersection_spec; split; auto. * inversion H0. rewrite <- (si_dst1 _ _ _ HH0); [| apply (@right_valid _ _ _ _ _ _ g (binGraph _)); auto]. destruct H7; rewrite H13; subst r. intro. apply (@valid_not_null _ _ _ _ g4 _ (maGraph _) null); auto; reflexivity. - pose proof LocalGraphCopy.labeledgraph_egen_ecopy1 g4 g4' (x, R) (x0, R) x0 r0. apply H10; clear H10; auto. subst r0. f_equal. inversion H0. rewrite (si_dst1 _ _ _ HH0); auto. apply (@right_valid _ _ _ _ _ _ g (binGraph _)); auto. + eapply is_guarded_BinMaFin'_labeledgraph_add_edge; [auto | | exact H8]. rewrite Same_set_spec; intro e; simpl. rewrite Intersection_spec. assert (e = (x0, R) <-> (x0, R) = e) by (split; intros; congruence). tauto. + simpl. unfold update_elabel; simpl. destruct_eq_dec (x, R) (x, R); auto; congruence. + subst g5'. simpl. unfold updateEdgeFunc. rewrite if_true; reflexivity. Qed.
imports: CertiGraph.lib.Ensembles_ext Coq.Lists.List VST.msl.seplog VST.msl.log_normalize VST.msl.ramification_lemmas VST.msl.Coqlib2 CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext CertiGraph.lib.relation_list CertiGraph.lib.Morphisms_ext CertiGraph.msl_ext.log_normalize CertiGraph.msl_ext.iter_sepcon CertiGraph.graph.graph_model CertiGraph.graph.path_lemmas CertiGraph.graph.reachable_computable CertiGraph.graph.reachable_ind CertiGraph.graph.graph_gen CertiGraph.graph.graph_relation CertiGraph.graph.subgraph2 CertiGraph.graph.dag CertiGraph.graph.weak_mark_lemmas CertiGraph.graph.graph_morphism CertiGraph.graph.local_graph_copy CertiGraph.msl_application.Graph CertiGraph.msl_application.GraphBin CertiGraph.msl_application.Graph_Copy Coq.Logic.Classical