aboutsummaryrefslogtreecommitdiffstats
path: root/matching.v
diff options
context:
space:
mode:
Diffstat (limited to 'matching.v')
-rw-r--r--matching.v29
1 files changed, 1 insertions, 28 deletions
diff --git a/matching.v b/matching.v
index 494bb92..cb09690 100644
--- a/matching.v
+++ b/matching.v
@@ -64,32 +64,6 @@ Definition matches (m : matcher) (bs : gmap string expr) :
64 snd <$> matches_aux ms bs 64 snd <$> matches_aux ms bs
65 end. 65 end.
66 66
67(* Copied from stdpp and changed so that the value types
68 of m1 and m2 are decoupled *)
69Lemma dom_subseteq_size' `{FinMapDom K M D} {A B} (m1 : M A) (m2 : M B) :
70 dom m2 ⊆ dom m1 → size m2 ≤ size m1.
71Proof.
72 revert m1. induction m2 as [|i x m2 ? IH] using map_ind; intros m1 Hdom.
73 { rewrite map_size_empty. lia. }
74 rewrite dom_insert in Hdom.
75 assert (i ∉ dom m2) by (by apply not_elem_of_dom).
76 assert (i ∈ dom m1) as [x' Hx']%elem_of_dom by set_solver.
77 rewrite <-(insert_delete m1 i x') by done.
78 rewrite !map_size_insert_None, <-Nat.succ_le_mono
79 by (by rewrite ?lookup_delete).
80 apply IH. rewrite dom_delete. set_solver.
81Qed.
82
83Lemma dom_empty_subset `{Countable K} `{FinMapDom K M D} {A B} (m : M A) :
84 dom m ⊆ dom (∅ : M B) → m = ∅.
85Proof.
86 intros Hdom.
87 apply dom_subseteq_size' in Hdom.
88 rewrite map_size_empty in Hdom.
89 inv Hdom.
90 by apply map_size_empty_inv.
91Qed.
92
93Lemma matches_aux_empty bs : matches_aux ∅ bs = Some (bs, ∅). 67Lemma matches_aux_empty bs : matches_aux ∅ bs = Some (bs, ∅).
94Proof. done. Qed. 68Proof. done. Qed.
95 69
@@ -496,8 +470,7 @@ Proof.
496 revert strict bs brs Hmatches. 470 revert strict bs brs Hmatches.
497 induction ms using map_ind; intros strict bs brs Hmatches. 471 induction ms using map_ind; intros strict bs brs Hmatches.
498 - destruct strict; simplify_option_eq. 472 - destruct strict; simplify_option_eq.
499 + apply dom_empty_subset in H0. simplify_eq. 473 + apply map_dom_empty_subset in H0. simplify_eq. constructor.
500 constructor.
501 + constructor. 474 + constructor.
502 - destruct x. 475 - destruct x.
503 + apply matches_step' in Hmatches as He. 476 + apply matches_step' in Hmatches as He.