theory BitCoded2

  imports "Lexer" 

begin

section \<open>Bit-Encodings\<close>

datatype bit = Z | S

fun 

  code :: "val \<Rightarrow> bit list"

where

  "code Void = []"

| "code (Char c) = []"

| "code (Left v) = Z # (code v)"

| "code (Right v) = S # (code v)"

| "code (Seq v1 v2) = (code v1) @ (code v2)"

| "code (Stars []) = [S]"

| "code (Stars (v # vs)) =  (Z # code v) @ code (Stars vs)"

fun 

  Stars_add :: "val \<Rightarrow> val \<Rightarrow> val"

where

  "Stars_add v (Stars vs) = Stars (v # vs)"

| "Stars_add v _ = Stars [v]" 

function

  decode' :: "bit list \<Rightarrow> rexp \<Rightarrow> (val * bit list)"

where

  "decode' ds ZERO = (Void, [])"

| "decode' ds ONE = (Void, ds)"

| "decode' ds (CHAR d) = (Char d, ds)"

| "decode' [] (ALT r1 r2) = (Void, [])"

| "decode' (Z # ds) (ALT r1 r2) = (let (v, ds') = decode' ds r1 in (Left v, ds'))"

| "decode' (S # ds) (ALT r1 r2) = (let (v, ds') = decode' ds r2 in (Right v, ds'))"

| "decode' ds (SEQ r1 r2) = (let (v1, ds') = decode' ds r1 in

                             let (v2, ds'') = decode' ds' r2 in (Seq v1 v2, ds''))"

| "decode' [] (STAR r) = (Void, [])"

| "decode' (S # ds) (STAR r) = (Stars [], ds)"

| "decode' (Z # ds) (STAR r) = (let (v, ds') = decode' ds r in

                                    let (vs, ds'') = decode' ds' (STAR r) 

                                    in (Stars_add v vs, ds''))"

by pat_completeness auto

lemma decode'_smaller:

  assumes "decode'_dom (ds, r)"

  shows "length (snd (decode' ds r)) \<le> length ds"

using assms

apply(induct ds r)

apply(auto simp add: decode'.psimps split: prod.split)

using dual_order.trans apply blast

by (meson dual_order.trans le_SucI)

termination "decode'"  

apply(relation "inv_image (measure(%cs. size cs) <*lex*> measure(%s. size s)) (%(ds,r). (r,ds))") 

apply(auto dest!: decode'_smaller)

by (metis less_Suc_eq_le snd_conv)

definition

  decode :: "bit list \<Rightarrow> rexp \<Rightarrow> val option"

where

  "decode ds r \<equiv> (let (v, ds') = decode' ds r 

                  in (if ds' = [] then Some v else None))"

lemma decode'_code_Stars:

  assumes "\<forall>v\<in>set vs. \<Turnstile> v : r \<and> (\<forall>x. decode' (code v @ x) r = (v, x)) \<and> flat v \<noteq> []" 

  shows "decode' (code (Stars vs) @ ds) (STAR r) = (Stars vs, ds)"

  using assms

  apply(induct vs)

  apply(auto)

  done

lemma decode'_code:

  assumes "\<Turnstile> v : r"

  shows "decode' ((code v) @ ds) r = (v, ds)"

using assms

  apply(induct v r arbitrary: ds) 

  apply(auto)

  using decode'_code_Stars by blast

lemma decode_code:

  assumes "\<Turnstile> v : r"

  shows "decode (code v) r = Some v"

  using assms unfolding decode_def

  by (smt append_Nil2 decode'_code old.prod.case)

section {* Annotated Regular Expressions *}

datatype arexp = 

  AZERO

| AONE "bit list"

| ACHAR "bit list" char

| ASEQ "bit list" arexp arexp

| AALTs "bit list" "arexp list"

| ASTAR "bit list" arexp

abbreviation

  "AALT bs r1 r2 \<equiv> AALTs bs [r1, r2]"

fun asize :: "arexp \<Rightarrow> nat" where

  "asize AZERO = 1"

| "asize (AONE cs) = 1" 

| "asize (ACHAR cs c) = 1"

| "asize (AALTs cs rs) = Suc (sum_list (map asize rs))"

| "asize (ASEQ cs r1 r2) = Suc (asize r1 + asize r2)"

| "asize (ASTAR cs r) = Suc (asize r)"

fun 

  erase :: "arexp \<Rightarrow> rexp"

where

  "erase AZERO = ZERO"

| "erase (AONE _) = ONE"

| "erase (ACHAR _ c) = CHAR c"

| "erase (AALTs _ []) = ZERO"

| "erase (AALTs _ [r]) = (erase r)"

| "erase (AALTs bs (r#rs)) = ALT (erase r) (erase (AALTs bs rs))"

| "erase (ASEQ _ r1 r2) = SEQ (erase r1) (erase r2)"

| "erase (ASTAR _ r) = STAR (erase r)"

lemma decode_code_erase:

  assumes "\<Turnstile> v : (erase  a)"

  shows "decode (code v) (erase a) = Some v"

  using assms

  by (simp add: decode_code) 

fun nonalt :: "arexp \<Rightarrow> bool"

  where

  "nonalt (AALTs bs2 rs) = False"

| "nonalt r = True"

fun good :: "arexp \<Rightarrow> bool" where

  "good AZERO = False"

| "good (AONE cs) = True" 

| "good (ACHAR cs c) = True"

| "good (AALTs cs []) = False"

| "good (AALTs cs [r]) = False"

| "good (AALTs cs (r1#r2#rs)) = (\<forall>r' \<in> set (r1#r2#rs). good r' \<and> nonalt r')"

| "good (ASEQ _ AZERO _) = False"

| "good (ASEQ _ (AONE _) _) = False"

| "good (ASEQ _ _ AZERO) = False"

| "good (ASEQ cs r1 r2) = (good r1 \<and> good r2)"

| "good (ASTAR cs r) = True"

fun fuse :: "bit list \<Rightarrow> arexp \<Rightarrow> arexp" where

  "fuse bs AZERO = AZERO"

| "fuse bs (AONE cs) = AONE (bs @ cs)" 

| "fuse bs (ACHAR cs c) = ACHAR (bs @ cs) c"

| "fuse bs (AALTs cs rs) = AALTs (bs @ cs) rs"

| "fuse bs (ASEQ cs r1 r2) = ASEQ (bs @ cs) r1 r2"

| "fuse bs (ASTAR cs r) = ASTAR (bs @ cs) r"

lemma fuse_append:

  shows "fuse (bs1 @ bs2) r = fuse bs1 (fuse bs2 r)"

  apply(induct r)

  apply(auto)

  done

fun intern :: "rexp \<Rightarrow> arexp" where

  "intern ZERO = AZERO"

| "intern ONE = AONE []"

| "intern (CHAR c) = ACHAR [] c"

| "intern (ALT r1 r2) = AALT [] (fuse [Z] (intern r1)) 

                                (fuse [S]  (intern r2))"

| "intern (SEQ r1 r2) = ASEQ [] (intern r1) (intern r2)"

fun retrieve :: "arexp \<Rightarrow> val \<Rightarrow> bit list" where

  "retrieve (AONE bs) Void = bs"

| "retrieve (ACHAR bs c) (Char d) = bs"

| "retrieve (AALTs bs [r]) v = bs @ retrieve r v" 

| "retrieve (AALTs bs (r#rs)) (Left v) = bs @ retrieve r v"

| "retrieve (AALTs bs (r#rs)) (Right v) = bs @ retrieve (AALTs [] rs) v"

| "retrieve (ASEQ bs r1 r2) (Seq v1 v2) = bs @ retrieve r1 v1 @ retrieve r2 v2"

| "retrieve (ASTAR bs r) (Stars []) = bs @ [S]"

| "retrieve (ASTAR bs r) (Stars (v#vs)) = 

     bs @ [Z] @ retrieve r v @ retrieve (ASTAR [] r) (Stars vs)"

fun

 bnullable :: "arexp \<Rightarrow> bool"

where

  "bnullable (AZERO) = False"

| "bnullable (AONE bs) = True"

| "bnullable (ACHAR bs c) = False"

| "bnullable (AALTs bs rs) = (\<exists>r \<in> set rs. bnullable r)"

| "bnullable (ASEQ bs r1 r2) = (bnullable r1 \<and> bnullable r2)"

| "bnullable (ASTAR bs r) = True"

fun 

  bmkeps :: "arexp \<Rightarrow> bit list"

where

  "bmkeps(AONE bs) = bs"

| "bmkeps(ASEQ bs r1 r2) = bs @ (bmkeps r1) @ (bmkeps r2)"

| "bmkeps(AALTs bs [r]) = bs @ (bmkeps r)"

| "bmkeps(AALTs bs (r#rs)) = (if bnullable(r) then bs @ (bmkeps r) else (bmkeps (AALTs bs rs)))"

fun

 bder :: "char \<Rightarrow> arexp \<Rightarrow> arexp"

where

  "bder c (AZERO) = AZERO"

| "bder c (AONE bs) = AZERO"

| "bder c (ACHAR bs d) = (if c = d then AONE bs else AZERO)"

| "bder c (AALTs bs rs) = AALTs bs (map (bder c) rs)"

| "bder c (ASEQ bs r1 r2) = 

     (if bnullable r1

      then AALT bs (ASEQ [] (bder c r1) r2) (fuse (bmkeps r1) (bder c r2))

      else ASEQ bs (bder c r1) r2)"

fun 

  bders :: "arexp \<Rightarrow> string \<Rightarrow> arexp"

where

  "bders r [] = r"

| "bders r (c#s) = bders (bder c r) s"

lemma bders_append:

  "bders r (s1 @ s2) = bders (bders r s1) s2"

  apply(induct s1 arbitrary: r s2)

  apply(simp_all)

  done

lemma bnullable_correctness:

  shows "nullable (erase r) = bnullable r"

  apply(induct r rule: erase.induct)

  apply(simp_all)

  done

lemma erase_fuse:

  shows "erase (fuse bs r) = erase r"

  apply(induct r rule: erase.induct)

  apply(simp_all)

  done

lemma erase_intern [simp]:

  shows "erase (intern r) = r"

  apply(induct r)

  apply(simp_all add: erase_fuse)

  done

lemma erase_bder [simp]:

  shows "erase (bder a r) = der a (erase r)"

  apply(induct r rule: erase.induct)

  apply(simp_all add: erase_fuse bnullable_correctness)

  done

lemma erase_bders [simp]:

  shows "erase (bders r s) = ders s (erase r)"

  apply(induct s arbitrary: r )

  apply(simp_all)

  done

lemma retrieve_encode_STARS:

  assumes "\<forall>v\<in>set vs. \<Turnstile> v : r \<and> code v = retrieve (intern r) v"

  shows "code (Stars vs) = retrieve (ASTAR [] (intern r)) (Stars vs)"

  using assms

  apply(induct vs)

  apply(simp_all)

  done

lemma retrieve_fuse2:

  assumes "\<Turnstile> v : (erase r)"

  shows "retrieve (fuse bs r) v = bs @ retrieve r v"

  using assms

  apply(induct r arbitrary: v bs)

         apply(auto elim: Prf_elims)[4]

   defer

  using retrieve_encode_STARS

   apply(auto elim!: Prf_elims)[1]

   apply(case_tac vs)

    apply(simp)

   apply(simp)

  (* AALTs  case *)

  apply(simp)

  apply(case_tac x2a)

   apply(simp)

   apply(auto elim!: Prf_elims)[1]

  apply(simp)

   apply(case_tac list)

   apply(simp)

  apply(auto)

  apply(auto elim!: Prf_elims)[1]

  done

lemma retrieve_fuse:

  assumes "\<Turnstile> v : r"

  shows "retrieve (fuse bs (intern r)) v = bs @ retrieve (intern r) v"

  using assms 

  by (simp_all add: retrieve_fuse2)

lemma r:

  assumes "bnullable (AALTs bs (a # rs))"

  shows "bnullable a \<or> (\<not> bnullable a \<and> bnullable (AALTs bs rs))"

  using assms

  apply(induct rs)

   apply(auto)

  done

lemma r0:

  assumes "bnullable a" 

  shows  "bmkeps (AALTs bs (a # rs)) = bs @ (bmkeps a)"

  using assms

  by (metis bmkeps.simps(3) bmkeps.simps(4) list.exhaust)

lemma r1:

  assumes "\<not> bnullable a" "bnullable (AALTs bs rs)"

  shows  "bmkeps (AALTs bs (a # rs)) = bmkeps (AALTs bs rs)"

  using assms

  apply(induct rs)

   apply(auto)

  done

lemma r2:

  assumes "x \<in> set rs" "bnullable x"

  shows "bnullable (AALTs bs rs)"

  using assms

  apply(induct rs)

   apply(auto)

  done

lemma  r3:

  assumes "\<not> bnullable r" 

          " \<exists> x \<in> set rs. bnullable x"

  shows "retrieve (AALTs bs rs) (mkeps (erase (AALTs bs rs))) =

         retrieve (AALTs bs (r # rs)) (mkeps (erase (AALTs bs (r # rs))))"

  using assms

  apply(induct rs arbitrary: r bs)

   apply(auto)[1]

  apply(auto)

  using bnullable_correctness apply blast

    apply(auto simp add: bnullable_correctness mkeps_nullable retrieve_fuse2)

   apply(subst retrieve_fuse2[symmetric])

  apply (smt bnullable.simps(4) bnullable_correctness erase.simps(5) erase.simps(6) insert_iff list.exhaust list.set(2) mkeps.simps(3) mkeps_nullable)

   apply(simp)

  apply(case_tac "bnullable a")

  apply (smt append_Nil2 bnullable.simps(4) bnullable_correctness erase.simps(5) erase.simps(6) fuse.simps(4) insert_iff list.exhaust list.set(2) mkeps.simps(3) mkeps_nullable retrieve_fuse2)

  apply(drule_tac x="a" in meta_spec)

  apply(drule_tac x="bs" in meta_spec)

  apply(drule meta_mp)

   apply(simp)

  apply(drule meta_mp)

   apply(auto)

  apply(subst retrieve_fuse2[symmetric])

  apply(case_tac rs)

    apply(simp)

   apply(auto)[1]

      apply (simp add: bnullable_correctness)

  apply (metis append_Nil2 bnullable_correctness erase_fuse fuse.simps(4) list.set_intros(1) mkeps.simps(3) mkeps_nullable nullable.simps(4) r2)

    apply (simp add: bnullable_correctness)

  apply (metis append_Nil2 bnullable_correctness erase.simps(6) erase_fuse fuse.simps(4) list.set_intros(2) mkeps.simps(3) mkeps_nullable r2)

  apply(simp)

  done

lemma t: 

  assumes "\<forall>r \<in> set rs. nullable (erase r) \<longrightarrow> bmkeps r = retrieve r (mkeps (erase r))" 

          "nullable (erase (AALTs bs rs))"

  shows " bmkeps (AALTs bs rs) = retrieve (AALTs bs rs) (mkeps (erase (AALTs bs rs)))"

  using assms

  apply(induct rs arbitrary: bs)

   apply(simp)

  apply(auto simp add: bnullable_correctness)

   apply(case_tac rs)

     apply(auto simp add: bnullable_correctness)[2]

   apply(subst r1)

     apply(simp)

    apply(rule r2)

     apply(assumption)

    apply(simp)

   apply(drule_tac x="bs" in meta_spec)

   apply(drule meta_mp)

    apply(auto)[1]

   prefer 2

  apply(case_tac "bnullable a")

    apply(subst r0)

     apply blast

    apply(subgoal_tac "nullable (erase a)")

  prefer 2

  using bnullable_correctness apply blast

  apply (metis (no_types, lifting) erase.simps(5) erase.simps(6) list.exhaust mkeps.simps(3) retrieve.simps(3) retrieve.simps(4))

  apply(subst r1)

     apply(simp)

  using r2 apply blast

  apply(drule_tac x="bs" in meta_spec)

   apply(drule meta_mp)

    apply(auto)[1]

   apply(simp)

  using r3 apply blast

  apply(auto)

  using r3 by blast

lemma asize0:

  shows "0 < asize r"

  apply(induct  r)

  apply(auto)

  done

lemma asize_fuse:

  shows "asize (fuse bs r) = asize r"

  apply(induct r)

  apply(auto)

  done

fun nonnested :: "arexp \<Rightarrow> bool"

  where

  "nonnested (AALTs bs2 []) = True"

| "nonnested (AALTs bs2 ((AALTs bs1 rs1) # rs2)) = False"

| "nonnested (AALTs bs2 (r # rs2)) = nonnested (AALTs bs2 rs2)"

| "nonnested r = True"

fun distinctBy :: "'a list \<Rightarrow> ('a \<Rightarrow> 'b) \<Rightarrow> 'b set \<Rightarrow> 'a list"

  where

  "distinctBy [] f acc = []"

| "distinctBy (x#xs) f acc = 

     (if (f x) \<in> acc then distinctBy xs f acc 

      else x # (distinctBy xs f ({f x} \<union> acc)))"

fun flts :: "arexp list \<Rightarrow> arexp list"

  where 

  "flts [] = []"

| "flts (AZERO # rs) = flts rs"

| "flts ((AALTs bs  rs1) # rs) = (map (fuse bs) rs1) @ flts rs"

| "flts (r1 # rs) = r1 # flts rs"

fun spill :: "arexp list \<Rightarrow> arexp list"

  where 

  "spill [] = []"

| "spill ((AALTs bs rs1) # rs) = (map (fuse bs) rs1) @ spill rs"

| "spill (r1 # rs) = r1 # spill rs"

lemma  spill_Cons:

  shows "spill (r # rs1) = spill [r] @ spill rs1"

  apply(induct r arbitrary: rs1)

   apply(auto)

  done

lemma  spill_append:

  shows "spill (rs1 @ rs2) = spill rs1 @ spill rs2"

  apply(induct rs1 arbitrary: rs2)

   apply(auto)

  by (metis append.assoc spill_Cons)

fun bsimp_ASEQ :: "bit list \<Rightarrow> arexp \<Rightarrow> arexp \<Rightarrow> arexp"

  where

  "bsimp_ASEQ _ AZERO _ = AZERO"

| "bsimp_ASEQ _ _ AZERO = AZERO"

| "bsimp_ASEQ bs1 (AONE bs2) r2 = fuse (bs1 @ bs2) r2"

| "bsimp_ASEQ bs1 r1 r2 = ASEQ  bs1 r1 r2"

fun bsimp_AALTs :: "bit list \<Rightarrow> arexp list \<Rightarrow> arexp"

  where

  "bsimp_AALTs _ [] = AZERO"

| "bsimp_AALTs bs1 [r] = fuse bs1 r"

| "bsimp_AALTs bs1 rs = AALTs bs1 rs"

fun bsimp :: "arexp \<Rightarrow> arexp" 

  where

  "bsimp (ASEQ bs1 r1 r2) = bsimp_ASEQ bs1 (bsimp r1) (bsimp r2)"

| "bsimp (AALTs bs1 rs) = bsimp_AALTs bs1 (flts (map bsimp rs))"

| "bsimp r = r"

inductive contains2 :: "arexp \<Rightarrow> bit list \<Rightarrow> bool" ("_ >>2 _" [51, 50] 50)

  where

  "AONE bs >>2 bs"

| "ACHAR bs c >>2 bs"

| "\<lbrakk>a1 >>2 bs1; a2 >>2 bs2\<rbrakk> \<Longrightarrow> ASEQ bs a1 a2 >>2 bs @ bs1 @ bs2"

| "r >>2 bs1 \<Longrightarrow> AALTs bs (r#rs) >>2 bs @ bs1"

| "AALTs bs rs >>2 bs @ bs1 \<Longrightarrow> AALTs bs (r#rs) >>2 bs @ bs1"

| "ASTAR bs r >>2 bs @ [S]"

| "\<lbrakk>r >>2 bs1; ASTAR [] r >>2 bs2\<rbrakk> \<Longrightarrow> ASTAR bs r >>2 bs @ Z # bs1 @ bs2"

| "r >>2 bs \<Longrightarrow> (bsimp r) >>2 bs"

inductive contains :: "arexp \<Rightarrow> bit list \<Rightarrow> bool" ("_ >> _" [51, 50] 50)