(* This file contains lemmas used by other pieces of the automation,
 * e.g. ChargeCore.Tactics.Tauto. It is a separate file so that
 * it does not pollute the global namespace when those modules are imported.
 *)
Require Export ChargeCore.Logics.ILogic.

Section logic.
  Context {L : Type}.
  Context {ILO : ILogicOps L}.
  Context {IL : ILogic L}.

  Theorem lcut : forall P Q R : L,
      P |-- R ->
      P |-- R -->> Q ->
      P |-- Q.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros.
(* Goal: @lentails L ILO P Q *)
    eapply landAdj in H0.
(* Goal: @lentails L ILO P Q *)
    etransitivity; [ | eassumption ].
(* Goal: @lentails L ILO P (@land L ILO P R) *)
    eapply landR. reflexivity. assumption.
  Qed.

  Theorem limplAdj_true : forall P Q,
      P |-- Q ->
      ltrue |-- P -->> Q.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. apply limplAdj. apply landL2. assumption.
  Qed.

  Theorem landAdj_true : forall P Q,
      ltrue |-- P -->> Q ->
      P |-- Q.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. apply landAdj in H. rewrite <- H.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
    apply landR. apply ltrueR. reflexivity.
  Qed.

  Lemma lapply : forall P Q R,
      P |-- Q -->> R ->
      P |-- Q ->
      P |-- R.
  Proof. intros; eapply lcut; eauto. Qed.

  Lemma lapply2 : forall P Q R S,
      P |-- Q -->> R -->> S ->
      P |-- Q ->
      P |-- R ->
      P |-- S.
  Proof. intros; eapply lcut; eauto using lapply. Qed.

  Lemma lapply3 : forall P Q R S T,
      P |-- Q -->> R -->> S -->> T ->
      P |-- Q ->
      P |-- R ->
      P |-- S ->
      P |-- T.
  Proof. intros; eapply lcut; eauto using lapply2. Qed.

  Lemma lapply4 : forall P Q R S T U,
      P |-- Q -->> R -->> S -->> T -->> U ->
      P |-- Q ->
      P |-- R ->
      P |-- S ->
      P |-- T ->
      P |-- U.
  Proof. intros; eapply lcut; eauto using lapply3. Qed.

  Lemma lapply5 : forall P Q R S T U V,
      P |-- Q -->> R -->> S -->> T -->> U -->> V ->
      P |-- Q ->
      P |-- R ->
      P |-- S ->
      P |-- T ->
      P |-- U ->
      P |-- V.
  Proof. intros; eapply lcut; eauto using lapply4. Qed.

  Lemma land_lor_distr_L : forall P Q R,
      P //\\ (Q \\// R) -|- (P //\\ Q) \\// (P //\\ R).
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. split.
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { rewrite landC. apply landAdj.
(* Goal: @lentails L ILO (@ltrue L ILO) (@limpl L ILO P Q) *)
      apply lorL; apply limplAdj.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR1. rewrite landC. reflexivity. }
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR2. rewrite landC. reflexivity. } }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { apply lorL; apply landR; try solve [ apply landL1 ; reflexivity ].
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR1. apply landL2. reflexivity. }
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR2. apply landL2. reflexivity. } }
  Qed.

  Lemma land_lor_distr_R : forall P Q R,
      (Q \\// R) //\\ P -|- (P //\\ Q) \\// (P //\\ R).
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. split.
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { apply landAdj.
(* Goal: @lentails L ILO (@ltrue L ILO) (@limpl L ILO P Q) *)
      apply lorL; apply limplAdj.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR1. rewrite landC. reflexivity. }
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR2. rewrite landC. reflexivity. } }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { apply lorL; apply landR; try solve [ apply landL1 ; reflexivity ].
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR1. apply landL2. reflexivity. }
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      { apply lorR2. apply landL2. reflexivity. } }
  Qed.

End logic.

(* Local definitions, for proving subsequent lemmas. *)
(* Goal: @lentails L ILO P (@land L ILO (@ltrue L ILO) P) *)
Local Ltac charge_split := apply landR.

Local Ltac charge_search_prems found :=
  match goal with
  | |- ?X |-- ?Y =>
    solve [ found
          | apply landL1 ; charge_search_prems found
          | apply landL2 ; charge_search_prems found ]
  end.

Local Ltac charge_assumption :=
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
  charge_search_prems reflexivity.

Local Ltac charge_intro :=
  first [ apply lforallR; intro
        | apply limplAdj_true
        | apply limplAdj ].

Local Ltac charge_intros :=
  repeat match goal with
         | |- _ |-- _ -->> _ =>
           charge_intro
         | |- _ |-- @lforall _ _ _ _ =>
           charge_intro
         end.

(* Goal: @lentails L ILO P (@ltrue L ILO) *)
(* Goal: @lentails L ILO P P *)
Local Ltac charge_trivial := apply ltrueR.

Local Ltac charge_use :=
  first [ eapply lapply; [ charge_assumption | ]
        | eapply lapply2; [ charge_assumption | | ]
        | eapply lapply3; [ charge_assumption | | | ]
        | eapply lapply4; [ charge_assumption | | | | ]
        | eapply lapply5; [ charge_assumption | | | | | ] ].

Local Ltac ends_with H ABC C :=
  let rec go k ABC :=
      match ABC with
      | C => k
      | _ -->> ?BC =>
        let k' := (k; first [ apply landAdj_true in H | apply landAdj in H ]) in
        go k' BC
      end
  in
  go ltac:(idtac) ABC.

Local Ltac charge_apply H :=
  match type of H with
  | _ |-- ?X =>
    match goal with
    | |- _ |-- ?Y =>
      ends_with H X Y ; etransitivity ; [ | eapply H ]
    end
  end.

Local Ltac charge_tauto :=
  repeat charge_split ;
  solve [ charge_assumption
        | charge_trivial
        | charge_intro; repeat charge_intro; charge_tauto
        | charge_split; solve [ charge_tauto ]
        | match goal with
          | H : _ |-- _ |- _ =>
            charge_apply H ; charge_tauto
          end
        | charge_use ; charge_tauto ].

Section logic2.
  Context {L : Type}.
  Context {ILO : ILogicOps L}.
  Context {IL : ILogic L}.

  Definition liff (A B : L) : L :=
    (A -->> B) //\\ (B -->> A).

  Local Notation "x <<-->> y" := (liff x y) (at level 78).

  Lemma ltrue_liff : forall A B,
      |-- A <<-->> B <-> A -|- B.
  Proof.
(* Goal: @lequiv L ILO (@land L ILO A B) (@land L ILO A C) *)
    unfold liff. split.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    { intros. split.
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
      { apply landAdj_true.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
        rewrite H. apply landL1. reflexivity. }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
      { apply landAdj_true.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
        rewrite H. apply landL2. reflexivity. } }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { intro. rewrite H.
(* Goal: @lentails L ILO (@limpl L ILO B A) (@limpl L ILO B A) *)
      apply landR; apply limplAdj_true; reflexivity. }
  Qed.

  Lemma land_cancel : forall A B C,
      A |-- B <<-->> C ->
      A //\\ B -|- A //\\ C.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. split.
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { charge_split; try charge_tauto.
      rewrite H. charge_tauto. }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { charge_split; try charge_tauto.
      rewrite H. charge_tauto. }
  Qed.

  Lemma uncurry : forall P Q R,
      (P //\\ Q -->> R) -|- (P -->> Q -->> R).
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. split.
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { charge_tauto. }
(* Goal: @lentails L ILO (@land L ILO A C) (@land L ILO A B) *)
    { charge_intro.
(* Goal: @lentails L ILO P Q *)
      eapply lapply. eapply lapply. charge_assumption.
      charge_tauto. charge_tauto. }
  Qed.

  Lemma forget_prem : forall P Q,
      |-- P -> Q |-- P.
  Proof. intros; charge_tauto. Qed.

  Lemma lrevert : forall P Q,
      |-- P -->> Q ->
      P |-- Q.
  Proof. intros; charge_tauto. Qed.

  Lemma charge_and_use : forall P Q C,
      C |-- P ->
      C //\\ P |-- Q ->
      C |-- P //\\ Q.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. charge_tauto.
  Qed.

  Lemma land_limpl_specialize_ap : forall P Q L R G,
      L //\\ R |-- P ->
      L //\\ Q //\\ R |-- G ->
      L //\\ (P -->> Q) //\\ R |-- G.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. charge_tauto.
  Qed.

  Lemma land_limpl_specializeR_ap : forall P Q R G,
      R |-- P ->
      Q //\\ R |-- G ->
      (P -->> Q) //\\ R |-- G.
  Proof.
(* Goal: @lentails L ILO (P x) (@limpl L ILO S R) *)
    intros; charge_tauto.
  Qed.

  Lemma land_limpl_specializeL_ap : forall P Q R G,
      R |-- P ->
      Q //\\ R |-- G ->
      R //\\ (P -->> Q) |-- G.
  Proof.
(* Goal: @lentails L ILO (P x) (@limpl L ILO S R) *)
    intros; charge_tauto.
  Qed.

  Lemma landA_ap : forall P Q R G,
      (P //\\ Q) //\\ R |-- G ->
      P //\\ Q //\\ R |-- G.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. charge_tauto.
  Qed.

  Lemma land_lexists_ap : forall T (P : T -> L) Q R S,
      (forall x, S //\\ P x //\\ Q |-- R) ->
      S //\\ (lexists P) //\\ Q |-- R.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. rewrite landC. rewrite landA.
(* Goal: @lentails L ILO (@land L ILO (@lor L ILO Q R) P) (@lor L ILO (@land L ILO P Q) (@land L ILO P R)) *)
    eapply landAdj.
(* Goal: @lentails L ILO (@lexists L ILO T P) (@limpl L ILO S R) *)
    apply lexistsL.
(* Goal: forall x : T, @lentails L ILO (P x) (@limpl L ILO S R) *)
    intro. specialize (H x).
(* Goal: @lentails L ILO (P x) (@limpl L ILO S R) *)
    charge_tauto.
  Qed.

  Lemma land_lexistsL_ap : forall T (P : T -> L) R S,
      (forall x, S //\\ P x |-- R) ->
      S //\\ (lexists P) |-- R.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros. rewrite landC.
(* Goal: @lentails L ILO (@land L ILO (@lor L ILO Q R) P) (@lor L ILO (@land L ILO P Q) (@land L ILO P R)) *)
    eapply landAdj.
(* Goal: @lentails L ILO (@lexists L ILO T P) (@limpl L ILO S R) *)
    apply lexistsL.
(* Goal: forall x : T, @lentails L ILO (P x) (@limpl L ILO S R) *)
    intro. specialize (H x).
(* Goal: @lentails L ILO (P x) (@limpl L ILO S R) *)
    charge_tauto.
  Qed.

  Lemma land_lexistsR_ap : forall T (P : T -> L) R S,
      (forall x, P x //\\ S |-- R) ->
      lexists P //\\ S |-- R.
  Proof.
(* Goal: forall (T : Type) (P : forall _ : T, L) (R S : L) (_ : forall x : T, @lentails L ILO (@land L ILO (P x) S) R), @lentails L ILO (@land L ILO (@lexists L ILO T P) S) R *)
    intros.
(* Goal: @lentails L ILO (@land L ILO (@lor L ILO Q R) P) (@lor L ILO (@land L ILO P Q) (@land L ILO P R)) *)
    eapply landAdj.
(* Goal: @lentails L ILO (@lexists L ILO T P) (@limpl L ILO S R) *)
    apply lexistsL.
(* Goal: forall x : T, @lentails L ILO (P x) (@limpl L ILO S R) *)
    intro. specialize (H x).
(* Goal: @lentails L ILO (P x) (@limpl L ILO S R) *)
    charge_tauto.
  Qed.

End logic2.

Notation "x <<-->> y" := (liff x y) (at level 78).
