From a8f2e9b4ccf0cb6ac8e2dabdfc0d28eecaed2f87 Mon Sep 17 00:00:00 2001
From: Yann Herklotz <git@yannherklotz.com>
Date: Tue, 12 Oct 2021 20:37:26 +0100
Subject: [sched] Add more lemmas into HashTree

---
 src/hls/Abstr.v    | 11 +----------
 src/hls/HashTree.v | 36 ++++++++++++++++++++++++++++++++++++
 2 files changed, 37 insertions(+), 10 deletions(-)

diff --git a/src/hls/Abstr.v b/src/hls/Abstr.v
index 58df532..a6b4505 100644
--- a/src/hls/Abstr.v
+++ b/src/hls/Abstr.v
@@ -741,15 +741,6 @@ Lemma sat_predicate_Pvar_inj :
     (forall c, sat_predicate (Pvar p1) c = sat_predicate (Pvar p2) c) -> p1 = p2.
 Proof. simplify. apply Pos2Nat.inj. eapply inj_asgn. eauto. Qed.
 
-Lemma hash_present_eq :
-  forall m e1 e2 p1 h h',
-    hash_value m e2 h = (p1, h') ->
-    h ! p1 = Some e1 ->
-    e1 = e2.
-Proof.
-  intros. unfold hash_value in *. destruct_match.
-  - inv H.
-
 Section CORRECT.
 
   Definition fd := @fundef RTLBlock.bb.
@@ -776,7 +767,7 @@ Section CORRECT.
 
     apply sat_predicate_Pvar_inj in H2; subst.
 
-    assert (e1 = e0) by admit; subst.
+    assert (e0 = e1) by (eapply hash_present_eq; eauto); subst.
 
     assert (forall e v v', sem_value ictx e v -> sem_value octx e v' -> v = v') by admit.
 
diff --git a/src/hls/HashTree.v b/src/hls/HashTree.v
index cb712e9..0aa0dd9 100644
--- a/src/hls/HashTree.v
+++ b/src/hls/HashTree.v
@@ -61,6 +61,13 @@ Proof.
   eapply in_map with (f := fst) in H. auto.
 Qed.
 
+Lemma max_not_present :
+  forall A k (h: PTree.t A), k > max_key h -> h ! k = None.
+Proof.
+  intros. destruct (h ! k) eqn:?; auto.
+  apply max_key_correct in Heqo. lia.
+Qed.
+
 Lemma filter_none :
   forall A f l (x: A), filter f l = nil -> In x l -> f x = false.
 Proof. induction l; crush; inv H0; subst; destruct_match; crush. Qed.
@@ -410,4 +417,33 @@ Module HashTree(H: Hashable).
     rewrite PTree.gso; solve [eauto | lia].
   Qed.
 
+  Lemma find_tree_Some :
+    forall el h v,
+      find_tree el h = Some v ->
+      h ! v = Some el.
+  Proof.
+    intros. unfold find_tree in *.
+    destruct_match; crush. destruct p.
+    destruct_match; crush.
+    match goal with
+    | H: filter ?f ?el = ?x::?xs |- _ =>
+      assert (In x (filter f el)) by (rewrite H; crush)
+    end.
+    apply PTree.elements_complete.
+    apply filter_In in H. inv H.
+    destruct_match; crush.
+  Qed.
+
+  Lemma hash_present_eq :
+    forall m e1 e2 p1 h h',
+      hash_value m e2 h = (p1, h') ->
+      h ! p1 = Some e1 -> e1 = e2.
+  Proof.
+    intros. unfold hash_value in *. destruct_match.
+    - inv H. apply find_tree_Some in Heqo.
+      rewrite Heqo in H0. inv H0. auto.
+    - inv H. assert (h ! (Pos.max m (max_key h) + 1) = None)
+        by (apply max_not_present; lia). crush.
+  Qed.
+
 End HashTree.
-- 
cgit