Theory TIGER_Intervals

(* Author: Basil Fürer *)

theory TIGER_Intervals
  imports TIGER_Pred_Algebra
begin

section ‹Character classes as interval lists›

text ‹A character class is a list of closed intervals ‹(lo, hi)› and denotes the
  characters in one of them. A well-formed class is sorted, and its intervals are
  nonempty, disjoint and nonadjacent. Owens et al. label transitions with character sets
  because iterating over a large alphabet such as Unicode is impractical
  cite‹‹Sect.~4.2› in "owens2009-regex-derivatives-reexamined"›. Lists of intervals
  are closed under the Boolean operations and so form an effective Boolean algebra
  cite‹‹Sect.~2› in "dantoni2014-minimization-symbolic-automata"›; single ranges
  are not cite‹‹Sect.~6.2› in "dantoni2014-minimization-symbolic-automata"›.

  The alphabet is a bounded discrete linear order (bytes, codepoints). Its bottom, top,
  successor and predecessor are parameters of the locale ‹discrete_order›,
  not a type class. Its axioms speak only about the range from bottom to top (typ‹nat›
  with a bound is an instance). The locale ‹bounded_discrete_order› adds that
  the range is the whole type.

  The operations accept any list and return well-formed classes. We prove their
  denotations relative to the range and interpret locale‹eba› in
  ‹bounded_discrete_order›. Negation is the gaps of the normal form, and
  conjunction follows from De Morgan's law. The instance on typ‹char› is in
  ‹TIGER_Tables› (an interpretation carries only the locale constants defined before it, so
  it follows the generator).›

type_synonym 'ch cls = ‹('ch × 'ch) list›

fun in_cls :: ‹'ch::ord cls ⇒ 'ch ⇒ bool› where
  ‹in_cls [] c ⟷ False›
| ‹in_cls ((l, h) # p) c ⟷ l ≤ c ∧ c ≤ h ∨ in_cls p c›

text ‹The denotation of a class depends only on its set of intervals:›

lemma in_cls_append[simp]: ‹in_cls (p @ q) c ⟷ in_cls p c ∨ in_cls q c›
  by (induct p c rule: in_cls.induct) auto

lemma in_cls_iff: ‹in_cls p c ⟷ (∃x ∈ set p. fst x ≤ c ∧ c ≤ snd x)›
  by (induct p c rule: in_cls.induct) auto

lemma in_cls_sort_key[simp]: ‹in_cls (sort_key f p) c ⟷ in_cls p c›
  by (simp add: in_cls_iff)

lemma not_in_cls_if_less: ‹∀x ∈ set p. c < fst x ⟹ ¬ in_cls p (c::'ch::linorder)›
  by (auto simp: in_cls_iff not_le)

fun sat_cls :: ‹'ch::ord cls ⇒ bool› where
  ‹sat_cls [] ⟷ False›
| ‹sat_cls ((l, h) # p) ⟷ l ≤ h ∨ sat_cls p›

text ‹A class is satisfiable when one of its intervals is nonempty:›

lemma sat_cls_iff: ‹sat_cls p ⟷ (∃c. in_cls p (c::'ch::order))›
  by (induct p rule: sat_cls.induct) (auto intro: order_trans)

subsection ‹The alphabet›

text ‹Within the range from ‹bot› to ‹top›, ‹succ c› is the least character above
  ‹c› and ‹pred c› the greatest below it:›

locale discrete_order =
  fixes bot :: ‹'ch::linorder›
    and top :: 'ch
    and succ :: ‹'ch ⇒ 'ch›
    and pred :: ‹'ch ⇒ 'ch›
  assumes bot_le_top: ‹bot ≤ top›
    and succ_le_iff: ‹c < top ⟹ succ c ≤ d ⟷ c < d›
    and le_pred_iff: ‹bot < c ⟹ d ≤ pred c ⟷ d < c›
begin

lemma less_succ: ‹c < top ⟹ c < succ c›
  using succ_le_iff[of c ‹succ c›] by simp

lemma succ_le_top: ‹c < top ⟹ succ c ≤ top›
  using succ_le_iff[of c top] by simp

lemma pred_less: ‹bot < c ⟹ pred c < c›
  using le_pred_iff[of c ‹pred c›] by simp

lemma succ_pred: ‹⟦ bot < c; c ≤ top ⟧ ⟹ succ (pred c) = c›
proof -
  assume ‹bot < c› ‹c ≤ top›
  then have ‹pred c < c› ‹pred c < top›
    using pred_less[of c] by auto
  then have ‹succ (pred c) ≤ c› ‹pred c < succ (pred c)›
    using succ_le_iff[of ‹pred c› c] less_succ[of ‹pred c›] by auto
  with ‹bot < c› show ?thesis
    using le_pred_iff[of c ‹succ (pred c)›] by auto
qed

subsection ‹Well-formed classes›

fun in_range :: ‹'ch cls ⇒ bool› where
  ‹in_range [] ⟷ True›
| ‹in_range ((l, h) # p) ⟷ bot ≤ l ∧ l ≤ h ∧ h ≤ top ∧ in_range p›

definition separated :: ‹'ch cls ⇒ bool› where
  ‹separated = sorted_wrt (λx y. snd x < top ∧ succ (snd x) < fst y)›

definition wf_cls :: ‹'ch cls ⇒ bool› where
  ‹wf_cls p ⟷ in_range p ∧ separated p›

text ‹A class is in range when its intervals are nonempty and lie between ‹bot› and
  ‹top›. It is separated when each interval ends before the successor of the end of
  every earlier one (so the intervals are sorted, disjoint and nonadjacent):›

lemma in_range_iff: ‹in_range p ⟷ (∀x ∈ set p. bot ≤ fst x ∧ fst x ≤ snd x ∧ snd x ≤ top)›
  by (induct p rule: in_range.induct) auto

lemma in_range_append[simp]: ‹in_range (p @ q) ⟷ in_range p ∧ in_range q›
  by (auto simp: in_range_iff)

lemma in_range_sort_key[simp]: ‹in_range (sort_key f p) ⟷ in_range p›
  by (simp add: in_range_iff)

subsection ‹Normal form›

definition clip :: ‹'ch cls ⇒ 'ch cls› where
  ‹clip p = filter (λ(l, h). l ≤ h) (map (λ(l, h). (max bot l, min h top)) p)›

text ‹Clipping cuts the intervals to the range and drops the empty ones:›

lemma in_range_clip: ‹in_range (clip p)›
  by (induct p rule: in_range.induct) (auto simp: clip_def)

lemma in_cls_clip: ‹in_cls (clip p) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c›
  by (induct p rule: in_range.induct) (auto simp: clip_def)

fun merge :: ‹'ch cls ⇒ 'ch cls› where
  ‹merge ((l, h) # (l', h') # p) =
    (if l' ≤ h ∨ l' = succ h then merge ((l, max h h') # p)
     else (l, h) # merge ((l', h') # p))›
| ‹merge p = p›

lemmas merge_induct = merge.induct[case_names Cons_Cons Nil Single]

text ‹Merging joins overlapping and adjacent neighbours of a list sorted by lower
  bounds. It keeps the first lower bound and takes the others from its input:›

lemma merge_hd: ‹p ≠ [] ⟹ merge p ≠ [] ∧ fst (hd (merge p)) = fst (hd p)›
  by (induct p rule: merge_induct) auto

lemma merge_ConsE:
  obtains h' p' where ‹merge ((l, h) # p) = (l, h') # p'›
  using merge_hd[of ‹(l, h) # p›] by (cases ‹merge ((l, h) # p)›) auto

lemma fst_merge_subset: ‹fst ` set (merge p) ⊆ fst ` set p›
  by (induct p rule: merge_induct) auto

lemma in_range_merge: ‹in_range p ⟹ in_range (merge p)›
  by (induct p rule: merge_induct) (auto simp: max_def)

lemma in_join_iff:
  assumes ‹l ≤ l'› ‹l' ≤ h ∨ l' = succ h› ‹h' ≤ top›
  shows ‹l ≤ c ∧ c ≤ max h h' ⟷ l ≤ c ∧ c ≤ h ∨ l' ≤ c ∧ c ≤ h'›
proof -
  have ‹l' ≤ c› if ‹h < c› ‹c ≤ h'›
    using assms that succ_le_iff[of h c] by auto
  with assms show ?thesis
    by (cases ‹c ≤ h›) (auto simp: max_def)
qed

lemma in_cls_merge:
  ‹⟦ sorted (map fst p); in_range p ⟧ ⟹ in_cls (merge p) c ⟷ in_cls p c›
proof (induct p rule: merge_induct)
  case (Cons_Cons l h l' h' p)
  show ?case
  proof (cases ‹l' ≤ h ∨ l' = succ h›)
    case True
    moreover from Cons_Cons.prems
    have ‹sorted (map fst ((l, max h h') # p))› ‹in_range ((l, max h h') # p)›
      by (auto simp: max_def)
    ultimately show ?thesis
      using Cons_Cons in_join_iff[of l l' h h' c] by auto
  next
    case False
    with Cons_Cons show ?thesis
      by auto
  qed
qed simp_all

lemma separated_merge: ‹⟦ sorted (map fst p); in_range p ⟧ ⟹ separated (merge p)›
proof (induct p rule: merge_induct)
  case (Cons_Cons l h l' h' p)
  show ?case
  proof (cases ‹l' ≤ h ∨ l' = succ h›)
    case True
    moreover from Cons_Cons.prems
    have ‹sorted (map fst ((l, max h h') # p))› ‹in_range ((l, max h h') # p)›
      by (auto simp: max_def)
    ultimately show ?thesis
      using Cons_Cons by auto
  next
    case False
    with Cons_Cons.prems have ‹h < top›
      by auto
    with False have ‹succ h < l'›
      using succ_le_iff[of h l'] by auto
    moreover have ‹l' ≤ fst x› if ‹x ∈ set (merge ((l', h') # p))› for x
      using that fst_merge_subset[of ‹(l', h') # p›] Cons_Cons.prems by fastforce
    ultimately show ?thesis
      using False Cons_Cons by (auto simp: separated_def intro: less_le_trans)
  qed
qed (simp_all add: separated_def)

definition cls_norm :: ‹'ch cls ⇒ 'ch cls› where
  ‹cls_norm p = merge (sort_key fst (clip p))›

text ‹The normal form of a class is well-formed and denotes its characters in range:›

lemma wf_cls_norm: ‹wf_cls (cls_norm p)›
  by (simp add: wf_cls_def cls_norm_def in_range_merge separated_merge in_range_clip)

lemma in_cls_norm: ‹in_cls (cls_norm p) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c›
  by (simp add: cls_norm_def in_cls_merge in_range_clip in_cls_clip)

subsection ‹Complement›

fun compl_from :: ‹'ch ⇒ 'ch cls ⇒ 'ch cls› where
  ‹compl_from c [] = [(c, top)]›
| ‹compl_from c ((l, h) # p) =
    (if c < l then [(c, pred l)] else []) @ (if h < top then compl_from (succ h) p else [])›

lemmas compl_from_induct = compl_from.induct[case_names Nil Cons]

text ‹The gaps of a well-formed class from ‹c› on are its complement from ‹c› to ‹top›:›

lemma in_cls_compl_from:
  assumes ‹wf_cls p› ‹∀x ∈ set p. c ≤ fst x› ‹bot ≤ c› ‹c ≤ top›
  shows ‹in_cls (compl_from c p) d ⟷ c ≤ d ∧ d ≤ top ∧ ¬ in_cls p d›
  using assms
proof (induct c p rule: compl_from_induct)
  case (Cons c l h p)
  from Cons.prems have ‹bot ≤ l› ‹l ≤ h› ‹h ≤ top› ‹c ≤ l› ‹wf_cls p›
    and above: ‹∀x ∈ set p. h < top ∧ succ h < fst x›
    by (simp_all add: wf_cls_def separated_def)
  have ih: ‹in_cls (compl_from (succ h) p) d ⟷ succ h ≤ d ∧ d ≤ top ∧ ¬ in_cls p d›
    if ‹h < top›
  proof -
    have ‹h < succ h› ‹succ h ≤ top›
      using that less_succ succ_le_top by auto
    with that ‹wf_cls p› above ‹bot ≤ l› ‹l ≤ h› show ?thesis
      by (intro Cons.hyps) auto
  qed
  have ‹¬ in_cls p d› if ‹d ≤ h›
    using above that less_succ[of h] by (intro not_in_cls_if_less) auto
  then show ?case
    using ‹c ≤ l› ‹l ≤ h› ‹h ≤ top› ‹bot ≤ c› ih le_pred_iff[of l d] succ_le_iff[of h d]
    by (cases ‹d < l›) auto
qed simp

lemma wf_compl_from:
  assumes ‹wf_cls p› ‹∀x ∈ set p. c ≤ fst x› ‹bot ≤ c› ‹c ≤ top›
  shows ‹wf_cls (compl_from c p) ∧ (∀x ∈ set (compl_from c p). c ≤ fst x)›
  using assms
proof (induct c p rule: compl_from_induct)
  case (Nil c)
  then show ?case
    by (simp add: wf_cls_def separated_def)
next
  case (Cons c l h p)
  from Cons.prems have ‹bot ≤ l› ‹l ≤ h› ‹h ≤ top› ‹c ≤ l› ‹wf_cls p›
    and above: ‹∀x ∈ set p. h < top ∧ succ h < fst x›
    by (simp_all add: wf_cls_def separated_def)
  define r where ‹r = (if h < top then compl_from (succ h) p else [])›
  have ‹wf_cls r ∧ (∀x ∈ set r. succ h ≤ fst x ∧ h < top)›
  proof (cases ‹h < top›)
    case True
    then have ‹h < succ h› ‹succ h ≤ top›
      using less_succ succ_le_top by auto
    with True ‹wf_cls p› above ‹bot ≤ l› ‹l ≤ h›
    have ‹wf_cls (compl_from (succ h) p) ∧ (∀x ∈ set (compl_from (succ h) p). succ h ≤ fst x)›
      by (intro Cons.hyps) auto
    with True show ?thesis
      by (simp add: r_def)
  qed (simp add: r_def wf_cls_def separated_def)
  then have ‹wf_cls r› ‹∀x ∈ set r. l < fst x›
    using ‹l ≤ h› less_succ[of h] by auto
  moreover have ‹compl_from c ((l, h) # p) = (if c < l then [(c, pred l)] else []) @ r›
    by (simp add: r_def)
  moreover have ‹pred l < top› ‹succ (pred l) = l› ‹c ≤ pred l› if ‹c < l›
  proof -
    from that ‹bot ≤ c› have ‹bot < l›
      by simp
    with that ‹l ≤ h› ‹h ≤ top› show ‹pred l < top› ‹succ (pred l) = l› ‹c ≤ pred l›
      using pred_less[of l] succ_pred[of l] le_pred_iff[of l c] by auto
  qed
  ultimately show ?case
    using ‹bot ≤ c› ‹c ≤ l›
    by (cases ‹c < l›) (auto simp: wf_cls_def separated_def sorted_wrt_append)
qed

subsection ‹The operations›

definition cls_top :: ‹'ch cls› where
  ‹cls_top = [(bot, top)]›

definition cls_bot :: ‹'ch cls› where
  ‹cls_bot = []›

definition cls_disj :: ‹'ch cls ⇒ 'ch cls ⇒ 'ch cls› where
  ‹cls_disj p q = cls_norm (p @ q)›

definition cls_neg :: ‹'ch cls ⇒ 'ch cls› where
  ‹cls_neg p = compl_from bot (cls_norm p)›

definition cls_conj :: ‹'ch cls ⇒ 'ch cls ⇒ 'ch cls› where
  ‹cls_conj p q = cls_neg (cls_disj (cls_neg p) (cls_neg q))›

text ‹The operations denote the Boolean operations on the range:›

lemma in_cls_top: ‹in_cls cls_top c ⟷ bot ≤ c ∧ c ≤ top›
  by (simp add: cls_top_def)

lemma in_cls_bot: ‹¬ in_cls cls_bot c›
  by (simp add: cls_bot_def)

lemma in_cls_disj: ‹in_cls (cls_disj p q) c ⟷ bot ≤ c ∧ c ≤ top ∧ (in_cls p c ∨ in_cls q c)›
  by (simp add: cls_disj_def in_cls_norm)

lemma in_cls_neg: ‹in_cls (cls_neg p) c ⟷ bot ≤ c ∧ c ≤ top ∧ ¬ in_cls p c›
proof -
  have ‹∀x ∈ set (cls_norm p). bot ≤ fst x›
    using wf_cls_norm by (simp add: wf_cls_def in_range_iff)
  then show ?thesis
    using wf_cls_norm bot_le_top by (auto simp: cls_neg_def in_cls_compl_from in_cls_norm)
qed

lemma in_cls_conj: ‹in_cls (cls_conj p q) c ⟷ bot ≤ c ∧ c ≤ top ∧ in_cls p c ∧ in_cls q c›
  by (auto simp: cls_conj_def in_cls_neg in_cls_disj)

text ‹All of them return well-formed classes:›

lemma wf_top: ‹wf_cls cls_top›
  by (simp add: cls_top_def wf_cls_def separated_def bot_le_top)

lemma wf_bot: ‹wf_cls cls_bot›
  by (simp add: cls_bot_def wf_cls_def separated_def)

lemma wf_disj: ‹wf_cls (cls_disj p q)›
  by (simp add: cls_disj_def wf_cls_norm)

lemma wf_neg: ‹wf_cls (cls_neg p)›
proof -
  have ‹∀x ∈ set (cls_norm p). bot ≤ fst x›
    using wf_cls_norm by (simp add: wf_cls_def in_range_iff)
  then show ?thesis
    using wf_compl_from wf_cls_norm bot_le_top by (simp add: cls_neg_def)
qed

lemma wf_conj: ‹wf_cls (cls_conj p q)›
  by (simp add: cls_conj_def wf_neg)

end

subsection ‹The effective Boolean algebra›

text ‹When the range is the whole type, character classes form an effective Boolean
  algebra:›

locale bounded_discrete_order = discrete_order +
  assumes bot_le: ‹bot ≤ c›
    and le_top: ‹c ≤ top›
begin

sublocale eba in_cls cls_top cls_bot cls_conj cls_disj cls_neg sat_cls
  by unfold_locales
    (simp_all add: bot_le le_top in_cls_top in_cls_bot in_cls_conj in_cls_disj in_cls_neg
      sat_cls_iff)

end

end