Module AssignD


Require Export ASCond.
Require Import Debugging.
Require Import Itv.

Require Import MSets.MSetPositive.
Require MSetDecide.
Module PositiveSetDecide := MSetDecide.Decide(PositiveSet).
Require MSetFacts.
Module Import PositiveSetFacts:=MSetFacts.Facts(PositiveSet).
Require Export Setoid.
Require Export Relation_Definitions.

Existing Instance PositiveSet.eq_equiv.

Module CoreAssign (N: NumSig) (Cond: ASCondSig N) (D: AbstractDomain N Cond) (R: HasRename N D).

  Import Cond.


  Definition encode (b:bool) (p:positive) :=
    if b
      then xI p
      else xO p.

  Definition decode (p:positive) :=
    match p with
      | xH => xH
      | xI p => p
      | xO p => p
    end.

  Lemma decode_encode_id b (p:positive) : decode (encode b p)=p.
Proof.
    unfold decode, encode; case b; simpl; auto.
  Qed.

  Hint Resolve decode_encode_id: vpl.

  Definition encodeE r x := encode (PositiveSet.mem x r) x.
  Definition encodeO r x := encode (negb (PositiveSet.mem x r)) x.


  Lemma encode_unalias: forall r x x0,
    (encodeO r x) <> (encodeE r x0).
Proof.
    unfold encodeO, encodeE; intros r x x0; case (PVar.eq_dec x0 x).
    - intros; subst; destruct (PositiveSet.mem x r); simpl; discriminate.
    - intros H1 H2; case H1; generalize H2; clear H1 H2.
    destruct (PositiveSet.mem x r); destruct (PositiveSet.mem x0 r); simpl; intro H; inversion H; auto.
  Qed.
  Hint Resolve encode_unalias: vpl.


  Definition decodeIn (r:PositiveSet.t) (aux m: Mem.t N.t) (p:positive) :=
    match p with
      | xH => (aux xH)
      | xI p => if PositiveSet.mem p r then m p else aux (xI p)
      | xO p => if PositiveSet.mem p r then aux (xO p) else m p
    end.

  Lemma decode_encodeE r aux m x: decodeIn r aux m (encodeE r x) = m x.
Proof.
    unfold decodeIn, encodeE, encode.
    elimtype (exists b, (PositiveSet.mem x r)=b); eauto.
    intro b; destruct b; intro H; rewrite H; simpl; rewrite H; simpl; auto.
  Qed.

  Hint Resolve decode_encodeE: vpl.
  Hint Rewrite decode_encodeE: vpl.

  Local Opaque PositiveSet.mem.

  Lemma decode_diff_encodeE r aux m x: x <> (encodeE r (decode x)) -> decodeIn r aux m x = aux x.
Proof.
    unfold decodeIn, encodeE, encode; destruct x as [p | p | ]; simpl;
      try (destruct (PositiveSet.mem p r); simpl; intuition).
    destruct (PositiveSet.mem 1 r); simpl; auto.
  Qed.

  Lemma decode_encodeO r aux m x: decodeIn r aux m (encodeO r x) = aux (encodeO r x).
Proof.
    unfold decodeIn, encodeO, encode.
    elimtype (exists b, (PositiveSet.mem x r)=b); eauto.
    intro b; destruct b; intro H; rewrite H; simpl; rewrite H; simpl; auto.
  Qed.

  Hint Rewrite decode_encodeO: vpl.

  Lemma decodeIn_simplify r aux1 m1 aux2 m2 x:
    (x=(encodeE r (decode x)) -> m1 (decode x) = m2 (decode x))
    ->(x<>(encodeE r (decode x)) -> aux1 x = aux2 x)
    -> decodeIn r aux1 m1 x = decodeIn r aux2 m2 x.
Proof.
    unfold decodeIn, encodeE, encodeO, encode; destruct x as [ p | p | ]; simpl;
      try (destruct (PositiveSet.mem p r); simpl; intros H H0; try (apply H0; intro; discriminate); intuition).
    case (PositiveSet.mem 1 r); simpl; intros H H0; try (apply H0; intro; discriminate); intuition.
  Qed.




  Fixpoint switch (m:PositiveSet.t) (i: positive) : PositiveSet.t :=
    match m with
      | PositiveSet.Leaf => PositiveSet.add i PositiveSet.Leaf
      | PositiveSet.Node l o r =>
        match i with
          | xH => PositiveSet.node l (negb o) r
          | xO p => PositiveSet.node (switch l p) o r
          | xI p => PositiveSet.node l o (switch r p)
        end
    end.

  Local Opaque PositiveSet.node.
  Local Transparent PositiveSet.mem.

  Lemma switch_out m: forall x y, y<>x -> PositiveSet.mem y (switch m x) = PositiveSet.mem y m.
Proof.
    induction m; simpl.
    + intros x y H. generalize (PositiveSet.add_spec PositiveSet.Leaf x y).
    unfold PositiveSet.In;
      destruct (PositiveSet.mem y (PositiveSet.add x PositiveSet.Leaf));
        destruct (PositiveSet.mem y PositiveSet.Leaf); intuition.
    + intro x; destruct x; simpl; intros y; rewrite PositiveSet.mem_node;
      destruct y; simpl; intuition.
  Qed.

  Lemma switch_in m: forall x, PositiveSet.mem x (switch m x) = negb (PositiveSet.mem x m).
Proof.
    induction m; simpl.
    + intros x; generalize (PositiveSet.add_spec PositiveSet.Leaf x x).
    unfold PositiveSet.In; simpl.
    cutrewrite (PositiveSet.mem x PositiveSet.Leaf = false); simpl.
    - destruct (PositiveSet.mem x (PositiveSet.add x PositiveSet.Leaf));
      intuition.
    - case x; simpl; auto.
    + intro x; destruct x; rewrite PositiveSet.mem_node; simpl; auto.
  Qed.
  Hint Rewrite switch_in: vpl.

  Local Opaque switch PositiveSet.mem.

  Lemma decode_sw_encodeE r aux m x:
    decodeIn (switch r x) aux m (encodeE r x) = aux (encodeE r x).
Proof.
    unfold decodeIn, encodeE, encode.
    elimtype (exists b, (PositiveSet.mem x r)=b); eauto.
    intro b; destruct b; intro H; rewrite H; simpl; rewrite switch_in; rewrite H; simpl; auto.
  Qed.

  Lemma decode_sw_encodeO r aux m x:
    decodeIn (switch r x) aux m (encodeO r x) = m x.
Proof.
    unfold decodeIn, encodeO, encode.
    elimtype (exists b, (PositiveSet.mem x r)=b); eauto.
    intro b; destruct b; intro H; rewrite H; simpl; rewrite switch_in; rewrite H; simpl; auto.
  Qed.
  Hint Rewrite decode_sw_encodeE decode_sw_encodeO: vpl.

  Lemma decode_sw_out r aux m x y:
    y <> (encodeE r x) -> y <> (encodeO r x) ->
    decodeIn (switch r x) aux m y =
    decodeIn r aux m y.
Proof.
    unfold decodeIn, encodeE, encodeO, encode.
    elimtype (exists b, (PositiveSet.mem x r)=b); eauto.
    intro b; destruct b; intro H; rewrite H; simpl;
      destruct y; intros H0 H1; try (rewrite switch_out); auto.
  Qed.


  Record assignDomain :=
    mk { pol: D.t ;
      renaming: PositiveSet.t
    }.

  Definition t:=assignDomain.

  Definition gamma (a:t) m := forall aux, D.gamma (pol a) (decodeIn (renaming a) aux m).


  Instance decodeIn_compat : Proper (PositiveSet.Equal ==>
    pointwise_relation PVar.t Logic.eq ==>
    pointwise_relation PVar.t Logic.eq ==>
    pointwise_relation PVar.t Logic.eq) decodeIn.
Proof.
    intros r1 r2 H1 aux1 aux2 H2 m1 m2 H3 x; subst.
    destruct x as [ p | p |]; simpl; try congruence;
        rewrite H1; case (PositiveSet.mem p r2); simpl; auto.
  Qed.

  Instance gamma_ext: Proper (Logic.eq ==> pointwise_relation PVar.t Logic.eq ==> iff) gamma.
Proof.
     eapply sat_compat_iff; unfold gamma.
     intros x y H m1 m2 H0 H1 aux. rewrite <- H. rewrite <- H0; auto.
  Qed.


  Definition top: t
    := {| pol := D.top ; renaming := PositiveSet.empty |}.

  Lemma top_correct: forall m, gamma top m.
    unfold gamma; simpl; auto with vpl.
  Qed.

  Definition bottom: t
    := {| pol := D.bottom ; renaming := PositiveSet.empty |}.

  Lemma bottom_correct m: gamma bottom m -> False.
    unfold gamma; simpl; intros.
    eapply D.bottom_correct.
    eapply (H m).
  Qed.
  Open Scope impure.
 
  Definition isBottom : t -> imp bool
    := fun p => D.isBottom (pol p).

  Lemma isBottom_correct : forall a, If isBottom a THEN forall m, gamma a m -> False.
Proof.
    unfold isBottom.
    VPLAsimplify.
    Grab Existential Variables.
    exact m.
  Qed.

  Definition assume (c:cond) (a: t) : imp t :=
  BIND res <- D.assume (map c (encodeE (renaming a))) (pol a) -;
  pure {| pol := res ;
          renaming := renaming a |}.

  Hint Unfold pointwise_relation.

  Lemma assume_correct (c:cond) (a:t): WHEN p <- assume c a THEN
    forall m, (sat c m) -> (gamma a m) -> gamma p m.
Proof.
    unfold gamma, assume; VPLAsimplify. simpl in * |- *.
    intros m H0 H1 aux; eapply H; auto.
    rewrite sat_map.
    erewrite (eval_pointwise_compat sat_mdo); eauto with vpl.
  Qed.
  Hint Resolve assume_correct: vpl.

  Definition assert (c:cond) (a: t) : imp bool := D.assert (map c (encodeE (renaming a))) (pol a).

  Lemma assert_correct (c:cond): forall (a:t), If assert c a THEN forall m, (gamma a m) -> (sat c m).
Proof.
    unfold gamma, assert. VPLAsimplify.
    intros m H0. generalize (H _ (H0 m)).
    rewrite sat_map.
    intros; erewrite (eval_pointwise_compat sat_mdo); eauto with vpl.
  Qed.
  Hint Resolve assert_correct: vpl.


  Definition project (a:t) (x:PVar.t) : imp t
    :=
     BIND res <- D.project (pol a) (encodeE (renaming a) x) -;
     pure {| pol := res ; renaming := (renaming a) |}.

  Lemma project_correct a x: WHEN p <- project a x THEN forall m v, gamma a m -> gamma p (Mem.assign x v m).
Proof.
    unfold project, gamma. VPLAsimplify. simpl in * |- *.
    intros m v H0 aux.
    eapply D.gamma_ext; [ eauto | idtac | idtac ].
    Focus 2.
    + eapply D.project_correct with (m:=decodeIn (renaming a) aux m) (v:=v);
      eauto.
    + intro x'; unfold Mem.assign at 2.
    case (PVar.eq_dec (encodeE (renaming a) x) x').
    - intro; subst. autorewrite with progvar vpl; auto.
    - intros; apply decodeIn_simplify; auto with vpl.
    intros; rewrite Mem.assign_out; auto.
    intro; subst x; intuition.
  Qed.



  Definition guassignAux x (c:cond) (a: t) : imp t :=
    let a:=trace DEBUG "guassign called" a in
    BIND tmp <- D.assume c (pol a) -;
    BIND aux <- D.project tmp (encodeE (renaming a) x) -;
    pure {| pol := aux ; renaming := switch (renaming a) x |}.

  Lemma guassignAux_correct x c a:
    let f:=(encodeE (renaming a)) in
    let c1:=(xmap c f (Mem.assign x (encodeO (renaming a) x) f)) in
    WHEN p <- guassignAux x c1 a THEN
        forall m v,
          xsat c m (Mem.assign x v m) ->
          gamma a m ->
            gamma p (Mem.assign x v m).
Proof.
    simpl; unfold guassignAux, trace; VPLAsimplify. simpl in * |- *. unfold gamma; intros m v Hxsat H1 aux.
    eapply D.gamma_ext; [ eauto | idtac | idtac ].
    Focus 2.
    + refine (H0 (decodeIn (renaming a) (Mem.assign (encodeO (renaming a) x) v aux) _) (aux (encodeE (renaming a) x)) _).
      eapply H; eauto.
    rewrite <- xsat_sat.
    rewrite xsat_xmap.
    erewrite (eval_pointwise_compat (xsat_old_mdo _)); eauto.
    erewrite (eval_pointwise_compat (xsat_new_mdo _)); eauto.
    - intros x'; simpl. autorewrite with vpl; auto.
    - intros x'. unfold Mem.assign at 2 3.
    case (PVar.eq_dec x x'); intros; autorewrite with progvar vpl; auto.
    + simpl; intro x'; unfold Mem.assign at 2.
    case (PVar.eq_dec (encodeE (renaming a) x) x').
    - intro; subst. autorewrite with vpl; auto.
    - intro H2. case (PVar.eq_dec x' (encodeO (renaming a) x)).
    * intros; subst; autorewrite with progvar vpl; auto.
    * intro H3; rewrite decode_sw_out; auto.
    apply decodeIn_simplify; auto with vpl.
    intros; rewrite Mem.assign_out; auto.
    intro; subst x; intuition.
    rewrite Mem.assign_out; auto.
  Qed.

  Definition guassign x (c:cond) (a: t) : imp t :=
    let f:=(encodeE (renaming a)) in
      let c1:=(xmap c f (Mem.assign x (encodeO (renaming a) x) f)) in
        guassignAux x c1 a.

  Local Hint Resolve guassignAux_correct: vpl.
  Opaque guassignAux.

  Lemma guassign_correct x c a:
    WHEN p <- guassign x c a THEN forall m v,
    xsat c m (Mem.assign x v m) ->
    gamma a m -> gamma p (Mem.assign x v m).
Proof.
    VPLAsimplify.
  Qed.

  Definition assign x te (a: t) : imp t :=
    let c:=(Atom Eq (Term.Var (encodeO (renaming a) x)) (Term.Old (Term.map te (encodeE (renaming a))))) in
      guassignAux x c a.

  Lemma assign_correct (x: PVar.t) (te: Term.t) (a:t): WHEN p <- assign x te a THEN
     forall m, gamma a m -> gamma p (Mem.assign x (Term.eval te m) m).
Proof.
    generalize (guassignAux_correct x (Atom Eq (Term.Var x) (Term.Old te)) a).
    simpl. VPLAsimplify.
    autorewrite with progvar in H.
    intros; eapply H; eauto with progvar.
  Qed.
  Hint Resolve guassign_correct assign_correct: vpl.


  Definition nop (x: PVar.t) a : imp t :=
    BIND res <- R.rename (encodeE (renaming a) x) (encodeO (renaming a) x) (pol a) -;
    pure {| pol := res ; renaming := switch (renaming a) x |}.
   
  Lemma nop_correct (x: PVar.t) (a:t):
    WHEN p <- nop x a THEN forall m, gamma a m -> gamma p m.
Proof.
    unfold nop, gamma; VPLAsimplify.
    intros; eapply R.rename_correct; eauto.
    autorewrite with vpl.
    eapply D.gamma_ext; [ eauto | idtac | eapply H with (aux:=Mem.assign (encodeO (renaming a) x) (m x) aux) ].
    intros x0.
    case (PVar.eq_dec (encodeE (renaming a) x) x0).
    - intros; subst; autorewrite with progvar vpl; auto.
    - intros. rewrite Mem.assign_out; auto.
      case (PVar.eq_dec (encodeO (renaming a) x) x0).
      + intros; subst; autorewrite with progvar vpl; auto.
      + intros. rewrite decode_sw_out; auto.
        intros; apply decodeIn_simplify; auto.
        intros; rewrite Mem.assign_out; auto.
  Qed.
  Local Hint Resolve nop_correct: vpl.

  Lemma nop_effect_1 (x: PVar.t) (a:t): WHEN p <- nop x a THEN PositiveSet.mem x (renaming p) = negb (PositiveSet.mem x (renaming a)).
Proof.
    unfold nop; xasimplify ltac:idtac.
    autorewrite with vpl.
    destruct (PositiveSet.mem x (renaming a)); simpl; intuition.
  Qed.

  Lemma nop_effect_2 (x y: PVar.t) (a:t): x <> y -> WHEN p <- nop x a THEN PositiveSet.mem y (renaming p) = (PositiveSet.mem y (renaming a)).
Proof.
    unfold nop; xasimplify ltac:idtac.
    intros; rewrite switch_out; intuition.
  Qed.

  Local Opaque nop.

  Definition switchAll (r:PositiveSet.t) (a:t) : imp t :=
    PositiveSet.fold (fun x0 k => bind k (nop x0))
                     r
                     (pure a).

  Lemma switchAll_correct r (a:t): WHEN p <- switchAll r a THEN forall m, gamma a m -> gamma p m.
Proof.
    unfold switchAll; rewrite PositiveSet.fold_spec.
    eapply wlp_forall; intro m.
    eapply wlp_forall; intro H.
    cut (WHEN p <- pure a THEN gamma p m).
    clear H.
    cut (forall x : PVar.t,
      PositiveSet.InL x (PositiveSet.elements r) ->
      PositiveSet.In x r).
    generalize (PositiveSet.elements_spec2w r).
    unfold PositiveSet.E.eq.
    generalize (PositiveSet.elements r).
    intros l H. generalize (pure a); clear a.
    induction H as [| a0 l H H0 IHl]; simpl.
    - auto.
    - intros. eapply IHl; eauto.
      VPLAsimplify.
    - intros; rewrite <- PositiveSet.elements_spec1; auto.
    - VPLAsimplify.
  Qed.

  Hint Rewrite SetoidList.InA_nil SetoidList.InA_cons: vplx.
  Hint Rewrite nop_effect_1: vplx.

  Lemma bool_eq_False b1 b2: (False <-> (b1=b2)) <-> b1 = negb b2.
Proof.
    case b1; case b2; simpl; intuition.
  Qed.

  Lemma negb_negb b : negb (negb b) = b.
Proof.
    case b; simpl; auto.
  Qed.

  Hint Rewrite bool_eq_False negb_negb: vplx.

  Lemma switchAll_effect r a x:
    WHEN p <- switchAll r a THEN
      (PositiveSet.In x r) <-> (PositiveSet.mem x (renaming p)) = negb (PositiveSet.mem x (renaming a)).
Proof.
    assert (WHEN p <- switchAll r a THEN
      PositiveSet.InL x (PositiveSet.elements r) <-> (PositiveSet.mem x (renaming p)) = negb (PositiveSet.mem x (renaming a))).
    unfold switchAll.
    rewrite PositiveSet.fold_spec.
    generalize (PositiveSet.elements_spec2w r).
    unfold PositiveSet.E.eq.
    generalize (PositiveSet.elements r).
    intros l H; generalize a; clear a.
    * induction H as [| x0 l H H0 IHl]; simpl; intro a.
    - VPLAsimplify. rewrite SetoidList.InA_nil, bool_eq_False, negb_negb. auto.
    - apply wlp_List_fold_left.
      VPLAsimplify.
      simpl in * |- *. intros H2; clear IHl.
      rewrite SetoidList.InA_cons.
      case (PVar.eq_dec x x0).
      + intro; subst.
        assert (X: (SetoidList.InA eq x0 l) <-> False).
        intuition.
        rewrite X in * |- *; clear X.
        rewrite bool_eq_False, negb_negb in H2.
        rewrite H2; clear H2; intuition.
        apply nop_effect_1; auto.
       + intros.
         rewrite H2; clear H2.
         generalize exta Hexta; clear exta Hexta H1 Hexta0.
         eapply wlp_monotone.
         eapply nop_effect_2; eauto.
         simpl. intros a1 H1 H2; rewrite H2; clear H2.
         intuition.
    * VPLAsimplify. simpl.
      intros a0; rewrite <- (PositiveSet.elements_spec1 r). auto.
  Qed.


  Lemma switchAll_effect_set r1 a:
       WHEN p <- (switchAll r1 a) THEN
         let r2:=(renaming a) in
         PositiveSet.Equal (renaming p) (PositiveSet.union (PositiveSet.diff r2 r1) (PositiveSet.diff r1 r2)).
Proof.
    unfold PositiveSet.Equal.
    apply wlp_forall. intros x.
    elimtype (exists r2, r2=(renaming a)); eauto.
    intros r2 H.
    eapply wlp_monotone.
    eapply switchAll_effect with (x:=x).
    simpl; intros p. generalize
      (PositiveSet.diff_spec r2 r1 x)
      (PositiveSet.diff_spec r1 r2 x)
      (PositiveSet.union_spec (PositiveSet.diff r2 r1) (PositiveSet.diff r1 r2) x).
    unfold PositiveSet.In; rewrite <- H; clear H.
    generalize (PositiveSet.mem x (renaming p)); intro b1.
    generalize (PositiveSet.mem x (PositiveSet.diff r2 r1)); intro b2.
    generalize (PositiveSet.mem x r2); intro b3.
    generalize (PositiveSet.mem x (PositiveSet.diff r1 r2)); intro b4.
    generalize (PositiveSet.mem x
      (PositiveSet.union (PositiveSet.diff r2 r1) (PositiveSet.diff r1 r2))); intro b5.
    generalize (PositiveSet.mem x r1); intro b6.
    generalize (PositiveSet.mem x r2); intro b7.
    destruct b1, b2, b3, b4, b5, b6; simpl; intuition.
  Qed.


  Lemma switchAll_prop1 r a:
      WHEN p <- switchAll (PositiveSet.diff (renaming a) r) a THEN
        PositiveSet.Equal (renaming p) (PositiveSet.inter (renaming a) r).
Proof.
    eapply wlp_monotone.
    eapply switchAll_effect_set.
    simpl.
    PositiveSetDecide.fsetdec.
  Qed.

  Lemma switchAll_prop2 r1 r2 a:
    WHEN p <- switchAll (PositiveSet.diff r2 r1) a THEN
      (PositiveSet.Equal (renaming a) (PositiveSet.inter r1 r2))
      -> (PositiveSet.Equal (renaming p) r2).
Proof.
    eapply wlp_monotone.
    eapply switchAll_effect_set.
    simpl.
    PositiveSetDecide.fsetdec.
  Qed.


  Definition isIncl (a1 a2:t): imp bool
    := let r1 := (PositiveSet.diff (renaming a1) (renaming a2)) in
       let r2 := (PositiveSet.diff (renaming a2) (renaming a1)) in
       BIND aux1 <- switchAll r1 a1 -;
       BIND aux2 <- switchAll r2 aux1 -;
        D.isIncl (pol aux2) (pol a2).

  Lemma isIncl_correct a1 a2: If isIncl a1 a2 THEN forall m, gamma a1 m -> gamma a2 m.
Proof.
    VPLAsimplify.
    intros m H0; assert (X: gamma exta0 m).
    - repeat (eapply switchAll_correct; eauto).
    - clear H0.
      unfold gamma.
      intros aux; generalize (X aux); clear X.
      cut (PositiveSet.Equal (renaming exta0) (renaming a2)).
      + intros X1 X2.
        rewrite <- X1; auto.
      + eapply switchAll_prop2; eauto.
        eapply switchAll_prop1; eauto.
  Qed.

  Definition join (a1 a2:t): imp t
    := let r1 := (PositiveSet.diff (renaming a1) (renaming a2)) in
        let r2 := (PositiveSet.diff (renaming a2) (renaming a1)) in
        BIND aux1 <- switchAll r1 a1 -;
        BIND aux2 <- switchAll r2 a2 -;
        BIND res <- D.join (pol aux1) (pol aux2) -;
        pure {| pol := res ; renaming := PositiveSet.inter (renaming a1) (renaming a2) |}.

  Lemma join_correct a1 a2: WHEN p <- join a1 a2 THEN forall m, gamma a1 m \/ gamma a2 m -> gamma p m.
Proof.
    unfold join; VPLAsimplify. simpl in * |- *.
    intros m H0 aux; simpl.
    case H0; clear H0; intro H0.
    * assert (H1: gamma exta m).
      eapply switchAll_correct; eauto.
      unfold gamma in H1.
      generalize (switchAll_prop1 (renaming a2) a1 _ Hexta).
      intro H2; rewrite <- H2; clear H2.
      eauto.
    * assert (H1: gamma exta0 m).
      eapply switchAll_correct; eauto.
      unfold gamma in H1.
      generalize (switchAll_prop1 (renaming a1) a2 _ Hexta0).
      intro X.
      eapply D.gamma_ext; [ eauto | idtac | eauto ].
      intros x; eapply decodeIn_compat; auto.
      rewrite X.
      PositiveSetDecide.fsetdec.
  Qed.


  Definition widen (a1 a2:t) : imp t :=
    let r1 := (PositiveSet.diff (renaming a1) (renaming a2)) in
    let r2 := (PositiveSet.diff (renaming a2) (renaming a1)) in
    BIND aux1 <- switchAll r1 a1 -;
    BIND aux2 <- switchAll r2 a2 -;
    BIND res <- D.widen (pol aux1) (pol aux2) -;
    pure {| pol := res ; renaming := PositiveSet.inter (renaming a1) (renaming a2) |}.

  Global Opaque assign join assume isIncl assert guassign project.
  Hint Resolve isIncl_correct top_correct join_correct bottom_correct project_correct
    assign_correct guassign_correct: vpl.


End CoreAssign.

Module Type CoreAssignSig (N: NumSig) (Cond: ASCondSig N) (D: AbstractDomain N Cond) (R: HasRename N D).

  Include CoreAssign N Cond D R.

End CoreAssignSig.


Module MakeAssign (N: NumSig) (Cond: ASCondSig N) (D: AbstractDomain N Cond) (R: HasRename N D) <: FullAbstractDomain N Cond
  := CoreAssign N Cond D R.

Module AssignLiftItv (N: NumSig) (Cond: ASCondSig N) (I: ItvSig N)
   (D: AbstractDomain N Cond) (R: HasRename N D) (DI: HasGetItv N Cond.Term I D)
   (CD: CoreAssignSig N Cond D R) <: HasGetItv N Cond.Term I CD.

  Import Cond DI.
  Import CD.

  Definition get_itv (te:Term.t) (a:t) := get_itv (Term.map te (encodeE (renaming a))) (pol a).

  Lemma get_itv_correct (te: Term.t) (a: t): WHEN i <- get_itv te a THEN
    forall m, gamma a m -> I.sat i (Term.eval te m).
Proof.
    unfold get_itv, gamma. VPLAsimplify. simpl.
 eliminate variable aux *) intros H m H0; generalize (H0 m); clear H0; intro H0.
    erewrite f_equal; eauto with vpl.
    erewrite Term.eval_map.
    apply (eval_pointwise_compat Term.eval_mdo); auto.
    intros x; autorewrite with vpl; auto.
  Qed.

End AssignLiftItv.

Module AssignSimplePrinting (N: NumSig) (Cond: ASCondSig N) (D: AbstractDomain N Cond) (R: HasRename N D) (DP: HasSimplePrinting N D)
   (Import CD: CoreAssignSig N Cond D R) <: HasSimplePrinting N CD.

  Definition pr (a:t) := DP.pr (pol a).

End AssignSimplePrinting.