archive-nl.com » NL » R » ROBBERTKREBBERS.NL

Total: 145

Choose link from "Titles, links and description words view":

Or switch to "Titles and links view".
  • Module values_refine
    vs τ s IH refine constructor eauto elim IH constructor auto Qed Lemma vals refine id Γ α Δ vs τ s Γ Δ vs τ s vs Γ α Δ vs τ s Proof induction 1 constructor eauto using val refine id Qed Lemma val refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 v1 v2 v3 τ τ Γ v1 Γ α1 f1 Δ1 Δ2 v2 τ v2 Γ α2 f2 Δ2 Δ3 v3 τ v1 Γ α1 α2 f2 f1 Δ1 Δ3 v3 τ Proof intros H Γ assert vs1 vs2 vs3 τ s τ s Forall3 λ v1 v2 τ v3 τ v2 Γ α2 f2 Δ2 Δ3 v3 τ v1 Γ α1 α2 f2 f1 Δ1 Δ3 v3 τ vs1 vs2 τ s vs2 Γ α2 f2 Δ2 Δ3 vs3 τ s vs1 Γ α1 α2 f2 f1 Δ1 Δ3 vs3 τ s intros vs1 ws2 vs3 τ s τ s Hvs revert vs3 τ s induction Hvs inversion clear 1 constructor eauto assert vs1 vs2 vs3 τ τ Forall2 λ v1 v2 v3 τ v2 Γ α2 f2 Δ2 Δ3 v3 τ v1 Γ α1 α2 f2 f1 Δ1 Δ3 v3 τ vs1 vs2 vs2 Γ α2 f2 Δ2 Δ3 vs3 τ vs1 Γ α1 α2 f2 f1 Δ1 Δ3 vs3 τ intros vs1 ws2 vs3 τ τ Hvs revert vs3 induction Hvs inversion clear 1 try constructor eauto intros Hv revert v3 τ induction Hv using val refine ind intros Hv refine inversion Hv decompose Forall hyps refine constructor eauto using base val refine compose Qed Lemma vals refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 vs1 vs2 vs3 τ s τ s Γ vs1 Γ α1 f1 Δ1 Δ2 vs2 τ s vs2 Γ α2 f2 Δ2 Δ3 vs3 τ s vs1 Γ α1 α2 f2 f1 Δ1 Δ3 vs3 τ s Proof intros Hvs revert vs3 τ s induction Hvs inversion clear 1 constructor eauto using val refine compose Qed Lemma val refine inverse Γ f Δ1 Δ2 v1 v2 τ v1 Γ false f Δ1 Δ2 v2 τ v2 Γ false meminj inverse f Δ2 Δ1 v1 τ Proof revert v1 v2 τ refine val refine ind simpl refine constructor eauto using base val refine inverse refine constructor eauto using Forall2 length l eq sym by apply Forall2 flip intros IH refine constructor eauto elim IH constructor eauto refine constructor eauto intros IH refine constructor eauto elim IH constructor eauto done Qed Lemma vals refine inverse Γ f Δ1 Δ2 vs1 vs2 τ s vs1 Γ false f Δ1 Δ2 vs2 τ s vs2 Γ false meminj inverse f Δ2 Δ1 vs1 τ s Proof induction 1 constructor eauto using val refine inverse Qed Lemma val refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 v1 v2 τ Γ v1 Γ α f Δ1 Δ2 v2 τ Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 Δ2 ₘ Δ2 meminj extend f f Δ1 Δ2 v1 Γ α f Δ1 Δ2 v2 τ Proof intros Hv intros induction Hv using val refine ind refine constructor eauto using base val refine weaken lookup compound weaken vals representable weaken Qed Lemma vals refine weaken Γ Γ α α f f Δ1 Δ2 Δ1 Δ2 vs1 vs2 τ s Γ vs1 Γ α f Δ1 Δ2 vs2 τ s Γ Γ α α Δ1 Γ α f Δ2 Δ1 ₘ Δ1 Δ2 ₘ Δ2 meminj extend f f Δ1 Δ2 vs1 Γ α f Δ1 Δ2 vs2 τ s Proof induction 2 constructor eauto using val refine weaken Qed Lemma val flatten refine Γ α f Δ1 Δ2 v1 v2 τ Γ v1 Γ α f Δ1 Δ2 v2 τ val flatten Γ v1 Γ α f Δ1 Δ2 val flatten Γ v2 Proof intros revert v1 v2 τ refine val refine ind simpl eauto using base val flatten refine intros τ n vs1 vs2 by apply Forall2 bind intros t τ s vs1 vs2 IH simpl generalize field bit sizes Γ τ s induction IH intros decompose Forall hyps auto eauto intros t τ s vs1 vs2 IH destruct vals representable as bits Γ Δ1 bit size of Γ unionT t vs1 τ s as bs1 Hbs1 eauto using bit size of union destruct vals representable as bits Γ Δ2 bit size of Γ unionT t vs2 τ s as bs2 Hbs2 eauto using bit size of union rewrite Hbs1 Hbs2 simpl eapply bits list join refine eauto elim IH simpl constructor auto intros t τ s i v1 v2 τ vs2 H τ Hv2 destruct α done destruct vals representable as bits Γ Δ2 bit size of Γ unionT t vs2 τ s as bs2 Hbs2 eauto using bit size of union rewrite Hbs2 simplify equality rewrite left id L meminj id f orb diag true apply bits refine compose with Δ2 resize bit size of Γ unionT t BIndet val flatten Γ v2 auto rewrite list lookup fmap H τ in Hv2 simplify equality rewrite resize le BIndet by done eauto 8 using bits subseteq refine Forall2 resize r flip Forall true val flatten unflatten Qed Lemma val unflatten refine Γ α f Δ1 Δ2 τ bs1 bs2 Γ Γ τ bs1 Γ α f Δ1 Δ2 bs2 length bs1 bit size of Γ τ val unflatten Γ τ bs1 Γ α f Δ1 Δ2 val unflatten Γ τ bs2 τ Proof intros H Γ H τ revert τ H τ bs1 bs2 refine type env ind H Γ intros τ b bs1 bs2 rewrite val unflatten base refine constructor by apply base val unflatten refine intros τ n IH Hn bs1 bs2 rewrite val unflatten array bit size of array intros Hbs Hbs refine constructor auto using array unflatten length revert bs1 bs2 Hbs Hbs clear Hn induction n simpl auto intros t τ s Ht IH bs1 bs2 erewrite val unflatten compound bit size of struct by eauto intros Hbs Hbs refine constructor eauto clear Ht unfold struct unflatten revert bs1 bs2 Hbs Hbs induction bit size of fields τ s H Γ intros decompose Forall hyps constructor auto assert Forall λ τ bit size of Γ τ length bs1 τ s rewrite Hbs eauto using bit size of union refine constructor eauto clear Hbs Ht induction IH decompose Forall hyps constructor eauto apply vals unflatten representable eauto using bits refine valid l apply vals unflatten representable eauto using bits refine valid r by erewrite Forall2 length by eauto Qed Lemma to val refine Γ α f Δ1 Δ2 w1 w2 τ Γ w1 Γ α f Δ1 Δ2 w2 τ to val Γ w1 Γ α f Δ1 Δ2 to val Γ w2 τ Proof intros H Γ Hw assert Γ Δ1 w1 τ as Hw1 by eauto using ctree refine typed l revert w1 τ Hw1 f Δ2 w2 Hw refine ctree typed ind intros τ b γ bs f Δ2 w2 Hw2 pattern w2 apply ctree refine inv l Hw2 simpl clear w2 Hw2 refine constructor eauto using base val unflatten refine pbits tag refine intros ws1 τ IH Hlen f Δ2 w2 Hw2 pattern w2 apply ctree refine inv l Hw2 simpl clear w2 Hw2 intros ws2 Hws refine constructor auto clear Hlen induction Hws decompose Forall hyps constructor auto intros t w γ bss1 τ s Ht IH Hlen f Δ2 w2 Hw2 pattern w2 apply ctree refine inv l Hw2 simpl clear w2 Hw2 intros w γ bss2 Hws simplify equality refine constructor eauto clear Hlen Ht induction Hws decompose Forall hyps constructor auto intros t i τ s w γ bs1 τ H τ IH Hlen f Δ2 w2 Hw2 pattern w2 apply ctree refine inv l Hw2 simpl clear w2 Hw2 intros simplify equality refine constructor eauto intros γ bs2 rewrite Forall2 app inv l intros γ bs2 γ bs2 decompose Forall hyps erewrite val unflatten compound by eauto refine constructor eauto by rewrite list lookup fmap H τ destruct α done rewrite right id L f orb diag true apply val refine compose with Δ1 val unflatten Γ τ tagged tag ctree flatten w τ auto erewrite to val unflatten ctree unflatten flatten by eauto using ctree typed type valid apply IH union reset above eauto using ctree refine id pbits refine shared rewrite fmap app take app alt by by erewrite ctree flatten length fmap length by eauto eauto using Forall2 length eauto using val unflatten refine pbits tag refine eapply vals unflatten representable eauto using pbits tag valid pbits refine valid r erewrite fmap length app length Forall2 length ctree flatten length Forall2 length by eauto rewrite Hlen eauto using bit size of union intros t τ s γ bs f Δ2 w2 Hw2 pattern w2 apply ctree refine inv l Hw2 simpl clear w2 Hw2 eauto using val unflatten refine pbits tag refine TCompound valid Qed Lemma of val refine Γ α f Δ1 Δ2 γ s v1 v2 τ Γ Forall sep unshared γ s length γ s bit size of Γ τ v1 Γ α f Δ1 Δ2 v2 τ of val Γ γ s v1 Γ α f Δ1 Δ2 of val Γ γ s v2 τ Proof intros H Γ H γ s H γ s Hvs apply ctree leaf refine refine eauto using of val typed val refine typed l val refine typed r seps unshared valid seps unshared unmapped revert v1 v2 τ Hvs γ s H γ s H γ s refine val refine ind intros simpl erewrite base val refine type of l base val refine type of r by eauto constructor eauto 6 using PBits refine seps unshared unmapped base val flatten refine seps unshared valid base val typed type valid intros τ n vs1 vs2 IH γ s H γ s simpl rewrite bit size of array intros H γ s constructor revert γ s H γ s H γ s induction IH intros decompose Forall hyps erewrite val refine type of l val refine type of r by eauto auto intros t τ s vs1 vs2 Ht Hvs IH γ s H γ s simpl erewrite bit size of struct by eauto intros H γ s clear Ht erewrite vals refine type of l vals refine type of r by eauto constructor revert vs1 vs2 γ s IH Hvs H γ s H γ s unfold field bit padding induction bit size of fields τ s H Γ do 2 inversion clear 1 intros decompose Forall hyps erewrite val refine type of l val refine type of r by eauto constructor eauto 7 clear IH revert vs1 vs2 γ s Hvs H γ s H γ s unfold field bit padding induction bit size of fields τ s H Γ inversion clear 1 intros decompose Forall hyps erewrite val refine type of l val refine type of r by eauto constructor eauto 7 using PBits BIndet refine seps unshared valid intros simpl erewrite val refine type of l val refine type of r by eauto constructor eauto using PBits BIndet refine PBits BIndet refine seps unshared valid constructor eapply PBits refine val flatten refine VUnionAll refine eauto using seps unshared valid seps unshared unmapped intros t τ s i v1 v2 τ vs2 Ht H τ Hv2 Hv12 IH γ s simpl assert Γ Δ1 v1 τ by eauto using val refine typed l assert Γ Δ2 v2 τ by eauto using val refine typed r simplify type equality destruct vals representable as bits Γ Δ2 bit size of Γ unionT t vs2 τ s as bs2 Hlen simpl eauto using bit size of union rewrite list lookup fmap H τ in Hv2 simplify equality constructor done auto using PBits unshared erewrite ctree flatten of val by eauto using val refine typed l rewrite zip with replicate r bit size of Γ unionT t bit size of Γ τ zip with app take drop by auto apply PBits refine auto using seps unshared valid seps unshared unmapped destruct α done apply Forall2 app l apply Forall2 replicate l eauto using Forall impl BIndet refine rewrite left id L f orb diag true eapply bits refine compose bits subseteq refine eauto using val flatten refine erewrite val flatten length by eauto eapply val flatten unflatten eauto using val typed type valid Qed Lemma of val to val refine Γ Δ w τ Γ Γ Δ w τ ctree Forall not sep unmapped w of val Γ tagged perm ctree flatten w to val Γ w Γ true Δ w τ Proof intros H Γ assert γ bs Γ Δ γ bs Forall not sep unmapped γ bs Forall not sep unmapped tagged perm γ bs eauto using pbits perm mapped Forall impl pbit valid sep valid assert γ bs Γ Δ γ bs Forall sep valid tagged perm γ bs intros eapply Forall fmap Forall impl eauto by intros assert γ bs Γ Δ γ bs Forall not sep unmapped tagged perm γ bs flip PBit BIndet tagged perm γ bs Γ true Δ γ bs intros γ bs rewrite zip with replicate r length γ bs by auto pattern γ bs at 3 rewrite PBits perm tag γ bs eapply PBits refine bits subseteq refine eauto using pbits tag valid base val flatten unflatten eapply Forall2 replicate l eauto using Forall true intros Hw Hw apply ctree leaf refine refine eauto 2 eapply of val typed eauto using to val typed ctree flatten valid revert w τ Hw Hw refine ctree typed ind simpl intros τ b γ bs rewrite base val unflatten type of by done constructor pattern γ bs at 3 rewrite PBits perm tag γ bs eapply PBits refine bits subseteq refine eauto using pbits tag valid base val flatten unflatten intros ws τ Hws IH Hlen constructor clear Hlen induction IH decompose Forall hyps erewrite type of correct fmap app take app alt drop app alt by eauto using to val typed auto intros t w γ bss τ s Ht Hws IH H γ bss Hindet Hlen rewrite list fmap compose erewrite fmap type of by eapply to vals typed Forall2 fmap l eauto constructor clear Ht clear H γ bss Hindet revert dependent w γ bss unfold field bit padding induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct fmap app associative L take app alt drop app alt by eauto using to val typed constructor auto clear IH Hindet revert dependent w γ bss unfold field bit padding induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct fmap app associative L drop app alt take app alt by eauto using to val typed constructor simpl auto intros t i τ s w γ bs τ Ht H τ s Hw IH Hlen decompose Forall hyps erewrite type of correct by eauto using to val typed rewrite fmap app take app alt drop app alt by auto constructor auto intros t τ s γ bs Ht H γ bs Hlen erewrite val unflatten compound by eauto simpl destruct vals representable as bits Γ Δ bit size of Γ unionT t λ τ val unflatten Γ τ take bit size of Γ τ tagged tag γ bs τ s τ s as bs Hbs eauto using bit size of union apply vals unflatten representable eauto using pbits tag valid rewrite fmap length Hlen eauto using bit size of union rewrite Hbs simpl constructor pattern γ bs at 2 rewrite PBits perm tag γ bs eapply PBits refine bits subseteq refine eauto using pbits tag valid eapply bits list join min bit size of Γ unionT t eauto using resize length assert Γ τ s as H τ s valid by eauto apply bit size of union in Ht auto clear Hbs induction H τ s valid decompose Forall hyps constructor eauto rewrite resize le BIndet by done eauto 8 using Forall2 resize r flip Forall true val flatten unflatten pbits tag valid Qed Lemma of val to val refine unflatten flatten Γ Δ w τ Γ Γ Δ w τ ctree Forall sep unshared w of val Γ tagged perm ctree flatten w to val Γ w Γ true Δ ctree unflatten Γ τ ctree flatten w τ Proof intros erewrite ctree unflatten flatten by eauto apply ctree refine compose true true meminj id meminj id Δ Δ with w eauto using of val to val refine union reset above ctree refine id seps unshared unmapped Qed Lemma val freeze refine l Γ Δ v τ Γ Γ Δ v τ freeze true v Γ true Δ v τ Proof intros revert v τ refine val typed ind simpl intros refine constructor eauto using base val freeze refine l intros vs τ IH refine constructor eauto elim IH csimpl auto intros t vs τ s IH refine constructor eauto elim IH constructor auto intros refine constructor eauto intros t vs τ s IH refine constructor eauto using vals representable freeze elim IH constructor auto Qed Lemma val new refine l Γ f Δ1 Δ2 v τ Γ Γ Δ2 v τ val union free v val new Γ τ Γ true f Δ1 Δ2 v τ Proof intros rewrite left id L meminj id f eapply val refine compose Γ true true eauto using val freeze refine l erewrite val unflatten flatten by eauto apply val unflatten refine eauto using val typed type valid apply BIndets refine eauto using val flatten valid Qed Lemma val new refine Γ α f Δ1 Δ2 τ Γ Γ τ val new Γ τ Γ α f Δ1 Δ2 val new Γ τ τ Proof intros apply val unflatten refine auto Qed Lemma val lookup seg refine Γ α f Δ1 Δ2 v1 v2 τ rs v3 Γ v1 Γ α f Δ1 Δ2 v2 τ v1 Γ rs

    Original URL path: http://robbertkrebbers.nl/research/ch2o/values_refine.html (2015-08-10)
    Open archived version from archive


  • Module values_separation
    H Γ Hv revert v τ Hv γ s1 γ s2 assert γ s bs list bit K Forall sep unmapped zip with PBit γ s bs length γ s 0 length bs length γ s Forall not sep unmapped γ s False unfold sep unmapped at 1 simpl intros rewrite Forall2 same length destruct 1 intros decompose Forall hyps naive solver refine val typed ind simpl constructor auto using PBits disjoint intros vs τ Hvs IH γ s1 γ s2 Hlen H γ s H γ s1 H γ s2 constructor rewrite bit size of array in Hlen revert γ s1 γ s2 Hlen H γ s H γ s1 H γ s2 induction IH decompose Forall hyps simplify type equality constructor rewrite zip with take zip with drop auto intros t vs τ s Ht Hvs IH γ s1 γ s2 Hlen H γ s H γ s1 H γ s2 erewrite bit size of struct in Hlen by eauto clear Ht erewrite fmap type of by eauto unfold field bit padding constructor revert vs γ s1 γ s2 Hvs IH Hlen H γ s H γ s1 H γ s2 induction bit size of fields τ s H Γ intros decompose Forall hyps simplify type equality constructor simpl rewrite zip with drop zip with take auto using PBits BIndet disjoint intros simplify type equality assert bit size of Γ τ 0 by eauto using bit size of ne 0 constructor erewrite zip with take zip with drop ctree flatten of val by eauto auto using PBits BIndet disjoint intros eauto constructor auto using PBits disjoint Qed Lemma of val union Γ γ s1 γ s2 v of val Γ γ s1 γ s2 v of val Γ γ s1 v of val Γ γ s2 v Proof revert v γ s1 γ s2 refine val ind alt simpl intros f equal auto using PBits union intros τ vs IH γ s1 γ s2 f equal revert γ s1 γ s2 induction IH intros f equal rewrite zip with take zip with drop auto intros s vs IH γ s1 γ s2 f equal revert γ s1 γ s2 generalize field bit padding Γ type of vs induction IH intros repeat f equal rewrite zip with drop zip with take auto using PBits BIndet union intros f equal rewrite zip with take zip with drop auto using PBits BIndet union intros f equal auto using PBits union Qed Lemma of val flatten disjoint Γ Δ w1 w2 v τ Γ Γ Δ w1 τ ctree unshared w1 ctree Forall not sep unmapped w1 Γ Δ v τ w1 w2 of val Γ tagged perm ctree flatten w1 v w2 Proof intros assert ctree unmapped w2 by eauto using ctree unshared unmapped assert Γ Δ w2 τ by eauto using ctree disjoint typed assert union free w2 by eauto using union free unmapped ctree typed sep valid erewrite union free reset w2 ctree unflatten flatten by eauto assert Forall

    Original URL path: http://robbertkrebbers.nl/research/ch2o/values_separation.html (2015-08-10)
    Open archived version from archive

  • Module memory
    Γ mem alloc list Γ os vs m 2 mem alloc list Γ os vs m os τ s 3 m ₘ mem alloc list Γ os vs m Proof rewrite Forall2 same length intros Hm Hfree Hovs Hvs revert τ s Hvs Hfree induction Hovs as o v os vs IH intros τ τ s inversion clear 2 as Ho Ho Hos decompose Forall hyps simplify type equality auto destruct IH τ s as eauto assert o dom indexset mem alloc list Γ os vs m rewrite mem dom alloc list elem of union elem of of list by eauto using Forall2 length tauto split ands eauto 6 using mem alloc valid perm full valid perm full mapped Forall2 impl val typed weaken mem alloc forward mem alloc allocable list mem alloc index typed memenv forward typed Qed Lemma mem alloc list index typed Γ m os vs τ s Γ Γ m Forall fresh dom indexset m os length os length vs Γ m vs τ s mem alloc list Γ os vs m os τ s Proof eapply mem alloc list valid Qed Lemma mem alloc list forward Γ m os vs τ s Γ Γ m Forall fresh dom indexset m os length os length vs Γ m vs τ s m ₘ mem alloc list Γ os vs m Proof eapply mem alloc list valid Qed Properties of the mem free fucntion Global Instance mem freeable perm dec o μ m Decision mem freeable perm o μ m Proof refine match cmap car m o as x return Decision w x Some Obj w μ ctree Forall λ γ b tagged perm γ b perm full w with Some Obj w μ cast if and decide μ μ decide ctree Forall λ γ b tagged perm γ b perm full w right end abstract naive solver Defined Global Instance mem freeable dec a m Decision mem freeable a m Lemma mem free memenv of m o mem free o m alter prod map id λ true o m Proof destruct m as m simpl apply map eq intros o destruct decide o o as rewrite lookup fmap lookup alter lookup fmap simpl by destruct m o as by rewrite lookup fmap lookup alter ne lookup fmap by done Qed Lemma mem erase freeable perm m o μ mem freeable perm o μ cmap erase m mem freeable perm o μ m Proof destruct m as m unfold mem freeable perm simpl rewrite lookup omap destruct m o as naive solver Qed Lemma mem dom free m o dom indexset mem free o m dom indexset m Proof destruct m as m simpl apply leibniz equiv dom alter Qed Lemma mem erase freeable m o mem freeable o cmap erase m mem freeable o m Proof unfold mem freeable by rewrite mem erase freeable perm Qed Lemma mem free index typed inv Δ o o τ alter prod map id λ true o Δ o τ Δ o τ Proof intros β destruct decide o o simplify map equality destruct Δ o as β eqn simplify equality by exists β by exists β simplify map equality Qed Lemma mem free index alive ne Δ o o o o index alive Δ o index alive alter prod map id λ true o Δ o Proof by intros τ exists τ simplify map equality Qed Lemma mem free index alive Δ o index alive alter prod map id λ bool true o Δ o Proof intros simplify map equality simplify option equality Qed Lemma mem free index alive inv Δ o o index alive alter prod map id λ true o Δ o index alive Δ o Proof by intros τ destruct decide o o exists τ simplify map equality simplify option equality Qed Lemma mem free forward Δ o Δ ₘ alter prod map id λ true o Δ Proof split eauto using mem free index alive inv intros o β destruct decide o o by exists true simplify map equality by exists β simplify map equality Qed Lemma mem free memenv compat Δ1 Δ2 o Δ1 ₘ Δ2 alter prod map id λ true o Δ1 ₘ alter prod map id λ true o Δ2 Proof intros Htyped Halive split eauto 4 using memenv forward typed mem free forward mem free index typed inv intros o τ β τ destruct decide o o simplify map equality simplify option equality destruct Halive o τ as τ by exists β by exists τ by exists τ simplify map equality Qed Lemma mem free forward least Γ Δ Δ m o μ mem freeable perm o μ m Γ Δ mem free o m Δ ₘ Δ alter prod map id λ true o Δ ₘ Δ Proof intros w split eauto using mem free index typed inv memenv forward typed intros o τ destruct decide o o as eauto using mem free index alive ne memenv forward alive mem free index typed inv intros τ destruct cmap valid Freed Γ Δ mem free o m o type of w as auto by destruct m simplify map equality by exists τ Qed Lemma mem free env valid Γ Δ o Γ Δ Γ alter prod map id λ true o Δ Proof intros H Δ o τ specialize H Δ o τ destruct decide o o simplify map equality destruct Δ o as eqn simplify map equality eapply H Δ do 2 red eauto Qed Lemma mem free valid Γ Δ m o Γ Γ Δ m Γ alter prod map id λ true o Δ mem free o m Proof destruct m as m intros H Γ Hm split ands simpl eauto using mem free env valid cmap valid memenv valid intros o τ rewrite lookup alter Some intros τ w μ simplify equality destruct cmap valid Freed Γ Δ CMap m o τ as eauto 10 using mem free forward memenv forward typed memenv forward alive destruct cmap valid Obj Γ Δ CMap m o w μ as simplify type equality eauto 11 using ctree typed type valid mem free index alive mem free forward memenv forward typed memenv forward alive destruct cmap valid Freed Γ Δ CMap m o τ as eauto 10 using mem free forward memenv forward typed memenv forward alive intros o w μ rewrite lookup alter Some intros simplify map equality destruct cmap valid Obj Γ Δ CMap m o w μ as τ eauto exists τ split ands eauto using ctree typed weaken mem free index alive ne mem free forward mem free forward memenv forward typed memenv forward alive Qed Lemma mem free valid Γ m o Γ Γ m Γ mem free o m Proof unfold valid at 2 3 cmap valid intros rewrite mem free memenv of eauto using mem free valid Qed Lemma mem free forward m o m ₘ mem free o m Proof rewrite mem free memenv of eauto using mem free forward Qed Lemma mem free valid index inv Γ Δ m μ o Γ Δ mem free o m mem freeable perm o μ m index alive Δ o Proof intros Hfree w by destruct Hfree o type of w by destruct m simplify map equality Qed Lemma mem foldr free forward m os m ₘ foldr mem free m os Proof induction os simpl eauto using mem free forward Qed Lemma mem foldr free valid Γ m os Γ Γ m Γ foldr mem free m os Proof induction os simpl auto using mem free valid Qed Lemma mem dom foldr free m os dom indexset foldr mem free m os dom indexset m Proof induction os simpl rewrite mem dom free auto Qed Lemma mem free free m o1 o2 mem free o1 mem free o2 m mem free o2 mem free o1 m Proof destruct m as m f equal destruct decide o1 o2 as auto using alter commute Qed Lemma mem free foldr free m o os mem free o foldr mem free m os foldr mem free mem free o m os Proof induction os simpl rewrite 1 mem free free auto with f equal Qed Lemma mem freeable perm free m o o μ o o mem freeable perm o μ m mem freeable perm o μ mem free o m Proof intros w exists w split ands auto by destruct m as m simplify map equality Qed Lemma mem freeable perm foldr free m o os μ o os mem freeable perm o μ m mem freeable perm o μ foldr mem free m os Proof induction os as o os IH simpl auto rewrite not elem of cons intros auto using mem freeable perm free Qed Properties of the lookup function Lemma mem lookup empty Γ a Γ a None val K Proof unfold lookupE mem lookup by rewrite cmap lookup empty Qed Lemma mem lookup typed Γ Δ m a v τ Γ Γ Δ m m Γ a Some v Γ Δ a TType τ Γ Δ v τ Proof unfold lookupE mem lookup intros Hm Hv Ha destruct m Γ a as w eqn simplify option equality eauto using to val typed Qed Lemma mem lookup frozen Γ Δ m a v Γ Γ Δ m m Γ a Some v frozen v Proof unfold lookupE mem lookup intros Hm Hv destruct m Γ a as w eqn simplify option equality eapply to val frozen cmap lookup Some eauto Qed Lemma mem lookup erase Γ m a cmap erase m Γ a option val K m Γ a Proof unfold lookupE mem lookup by rewrite cmap lookup erase Qed Lemma mem lookup alloc Γ Δ m o μ γ v τ Γ Γ Δ v τ Some Readable perm kind γ mem alloc Γ o μ γ v m Γ addr top o τ Some freeze true v Proof unfold lookupE mem lookup lookupE cmap lookup intros assert ctree Forall λ γ b Some Readable pbit kind γ b of val Γ replicate bit size of Γ τ γ v erewrite ctree flatten of val by eauto generalize val flatten Γ v induction bit size of Γ τ intros simpl constructor auto rewrite option guard True by eauto using addr top strict destruct m as m simplify map equality simplify type equality rewrite decide True by eauto using addr top is obj simpl by erewrite option guard True to of val by eauto Qed Lemma mem lookup weaken Γ1 Γ2 Δ m a v τ Γ1 Γ1 Δ m Γ1 Δ a TType τ m Γ1 a Some v Γ1 Γ2 m Γ2 a Some v Proof unfold lookupE mem lookup rewrite bind Some intros w erewrite cmap lookup weaken by eauto simplify option equality by erewrite to val weaken by eauto Qed Properties of the force function Lemma mem forced force Γ m a mem forced Γ a m mem force Γ a m m Proof done Qed Lemma mem force memenv of Γ Δ m a Γ Γ Δ m is Some m Γ a mem force Γ a m m Proof unfold mem force lookupE mem lookup simpl unfold lookupE cmap lookup intros v by destruct m Γ as w eqn simplify option equality eauto using cmap alter ref memenv of Qed Lemma mem force forward Γ Δ m a Γ Γ Δ m is Some m Γ a m ₘ mem force Γ a m Proof intros by erewrite mem force memenv of by eauto Qed Lemma mem force valid Γ Δ m a Γ Γ Δ m is Some m Γ a Γ Δ mem force Γ a m Proof unfold mem force lookupE mem lookup simpl unfold lookupE cmap lookup intros v case option guard simplify equality destruct m Γ as w eqn simplify equality destruct cmap lookup ref Some Γ Δ m addr index a addr ref Γ a w as eauto eapply cmap alter ref valid eauto eapply type of typed eauto case decide simplify equality case option guard simplify equality eapply ctree Forall not eauto using pbits mapped destruct w Γ as w eqn simplify option equality intros eapply ctree Forall not w eauto using ctree lookup byte Forall pbit unmapped indetify pbits mapped ctree lookup byte typed Qed Lemma mem force valid Γ m a Γ Γ m is Some m Γ a Γ mem force Γ a m Proof unfold valid at 2 3 cmap valid intros erewrite mem force memenv of by eauto eauto using mem force valid Qed Lemma mem force weaken Γ1 Γ2 Δ m a τ Γ1 Γ1 Γ2 Γ1 Δ m Γ1 Δ a TType τ mem force Γ1 a m mem force Γ2 a m Proof unfold mem force intros erewrite addr ref weaken by eauto eauto using cmap alter ref weaken Qed Lemma mem forced weaken Γ1 Γ2 Δ m a τ Γ1 Γ1 Γ2 Γ1 Δ m Γ1 Δ a TType τ mem forced Γ1 a m mem forced Γ2 a m Proof unfold mem forced intros by erewrite mem force weaken by eauto Qed Lemma mem erase force Γ m a cmap erase mem force Γ a m mem force Γ a cmap erase m Proof apply cmap erase alter ref Qed Lemma mem forced erase Γ a m mem forced Γ a cmap erase m mem forced Γ a m Proof unfold mem forced split intros Hm by rewrite mem erase force Hm destruct m as m simplify equality f equal apply map eq intros o destruct decide o addr index a simplify map equality auto apply f equal addr index a in Hm simplify map equality destruct m as simplify equality congruence Qed Lemma mem lookup force Γ Δ m a v τ Γ Γ Δ m Γ Δ a TType τ m Γ a Some v addr is obj a mem force Γ a m Γ a Some v Proof unfold mem force lookupE mem lookup simpl unfold lookupE cmap lookup intros case option guard simplify equality destruct m Γ as w eqn simplify equality by erewrite cmap lookup ref alter by eauto using cmap lookup ref le ref freeze le r simplify option equality Qed Lemma mem lookup force disjoint Γ Δ m a1 a2 τ2 v1 Γ Γ Δ m a1 Γ a2 m Γ a1 Some v1 mem force Γ a2 m Γ a1 Some v1 Proof unfold mem force lookupE mem lookup simpl unfold lookupE cmap lookup intros Ha case option guard simplify equality destruct m Γ addr index a1 as w1 eqn simplify equality destruct Ha as erewrite cmap lookup ref alter disjoint by eauto auto by erewrite cmap lookup ref alter by eauto using cmap lookup ref le ref freeze le r Qed Lemma mem force commute Γ m a1 a2 a1 Γ a2 mem force Γ a1 mem force Γ a2 m mem force Γ a2 mem force Γ a1 m Proof unfold mem force intros Hr auto using cmap alter ref commute by rewrite cmap alter ref le addr ref Γ a1 Hr cmap alter ref le freeze true addr ref Γ a2 addr ref Γ a2 cmap alter ref compose by eauto using ref freeze le l Qed Lemma mem force forced Γ m a mem forced Γ a mem force Γ a m Proof unfold mem forced mem force by rewrite cmap alter ref compose Qed Lemma mem dom force Γ m a dom indexset mem force Γ a m dom indexset m Proof destruct m simpl apply leibniz equiv dom alter Qed Properties of the insert function Lemma mem writable strict Γ m a mem writable Γ a m addr strict Γ a Proof intros w eauto using cmap lookup strict Qed Lemma mem writable alive Γ Δ m a Γ Γ Δ m mem writable Γ a m index alive Δ addr index a Proof intros Hm w assert Γ Δ w type of w by eauto using cmap lookup Some unfold lookupE cmap lookup lookupE cmap lookup ref in case option guard simplify equality destruct cmap car m addr index a as w μ eqn simplify equality destruct cmap valid Obj Γ Δ m addr index a w μ as τ auto Qed Global Instance mem writable dec Γ a m Decision mem writable Γ a m Proof refine match Some dec m Γ a with inleft w cast if decide ctree Forall λ γ b Some Writable pbit kind γ b w inright right end abstract unfold mem writable naive solver Defined Lemma mem writable lookup Γ m a mem writable Γ a m v m Γ a Some v Proof unfold lookupE mem lookup intros w simpl exists to val Γ w by rewrite option guard True by eauto using pbits kind weaken Qed Lemma mem lookup writable Γ m a m Γ a None mem writable Γ a m Proof intros destruct mem writable lookup Γ m a naive solver Qed Lemma of val flatten typed Γ Δ w v τ Γ Γ Δ w τ Γ Δ v τ ctree Forall λ γ b Some Writable pbit kind γ b w Γ Δ of val Γ tagged perm ctree flatten w v τ Proof intros eapply of val typed eauto eauto using pbits valid perm valid ctree flatten valid eapply pbits perm mapped pbits mapped eauto using pbits kind weaken pbits valid sep valid ctree flatten valid Qed Hint Resolve of val flatten typed Lemma of val flatten mapped Γ Δ w v τ Γ Γ Δ w τ Γ Δ v τ ctree Forall λ γ b Some Writable pbit kind γ b w ctree Forall not sep unmapped of val Γ tagged perm ctree flatten w v Proof intros eapply of val mapped eauto eapply pbits perm mapped pbits mapped eauto using pbits kind weaken pbits valid sep valid ctree flatten valid Qed Lemma of val flatten unshared Γ Δ w v τ Γ Γ Δ w τ Γ Δ v τ ctree Forall λ γ b Some Writable pbit kind γ b w ctree unshared of val Γ tagged perm ctree flatten w v Proof intros eapply of val unshared eauto eapply pbits perm unshared pbits unshared eauto using pbits kind weaken pbits valid sep valid ctree flatten valid eapply pbits perm mapped pbits mapped eauto using pbits kind weaken pbits valid sep valid ctree flatten valid Qed Lemma mem insert memenv of Γ Δ m a v τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m Γ Δ v τ a v Γ m m Proof unfold insertE mem insert lookupE mem lookup intros w eapply cmap alter memenv of eauto by erewrite of val type of type of correct by eauto Qed Lemma mem insert forward Γ Δ m a v τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m Γ Δ v τ m ₘ a v Γ m Proof intros by erewrite mem insert memenv of by eauto Qed Lemma mem insert valid Γ Δ m a v τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m Γ Δ v τ Γ Δ a v Γ m Proof intros w assert Γ Δ w τ by eauto eapply cmap alter valid eauto simplify type equality eauto using of val flatten mapped ctree Forall not ctree lookup Some Qed Lemma mem insert valid Γ m a v τ Γ Γ m Γ m a TType τ mem writable Γ a m Γ m v τ Γ a v Γ m Proof unfold valid at 2 3 cmap valid intros erewrite mem insert memenv of by eauto eauto using mem insert valid Qed Lemma mem erase insert Γ m a v cmap erase a v Γ m a v Γ cmap erase m Proof apply cmap erase alter Qed We need addr is obj a because writes at padding bytes are ignored Lemma mem lookup insert Γ Δ m a v τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m addr is obj a Γ Δ v τ a v Γ m Γ a Some freeze true v Proof unfold insertE lookupE mem insert mem lookup intros w Hw erewrite cmap lookup alter by eauto csimpl assert ctree Forall λ γ b Some Readable pbit kind γ b of val Γ tagged perm ctree flatten w v erewrite ctree flatten of val by eauto generalize val flatten Γ v induction Hw intros simpl constructor auto by transitivity Some Writable by erewrite option guard True to of val by eauto Qed Lemma mem lookup insert disjoint Γ Δ m a1 a2 v1 v2 τ2 Γ Γ Δ m a1 Γ a2 m Γ a1 Some v1 Γ Δ a2 TType τ2 mem writable Γ a2 m Γ Δ v2 τ2 a2 v2 Γ m Γ a1 Some v1 Proof unfold insertE lookupE mem insert mem lookup intros w2 Hw2 destruct m Γ a1 as w1 eqn simplify equality by erewrite cmap lookup alter disjoint by eauto using of val flatten unshared Qed Lemma mem insert commute Γ Δ m a1 a2 v1 v2 τ1 τ2 Γ Γ Δ m a1 Γ a2 Γ Δ a1 TType τ1 mem writable Γ a1 m Γ Δ v1 τ1 Γ Δ a2 TType τ2 mem writable Γ a2 m Γ Δ v2 τ2 a1 v1 Γ a2 v2 Γ m a2 v2 Γ a1 v1 Γ m Proof intros eapply cmap alter commute eauto Qed Lemma mem insert force commute Γ m a1 a2 v1 a1 Γ a2 a1 v1 Γ mem force Γ a2 m mem force Γ a2 a1 v1 Γ m Proof unfold mem force insertE mem insert cmap alter intros Hr auto using cmap alter ref commute by rewrite cmap alter ref le addr ref Γ a1 Hr cmap alter ref le freeze true addr ref Γ a2 addr ref Γ a2 cmap alter ref compose by eauto using ref freeze le l Qed Lemma mem insert force Γ m a v a v Γ mem force Γ a m a v Γ m Proof unfold insertE mem insert mem force cmap alter by rewrite cmap alter ref compose Qed Lemma mem insert forced Γ m a v mem forced Γ a a v Γ m Proof symmetry apply cmap alter ref compose id Qed Lemma mem insert writable Γ Δ m a1 a2 v2 τ2 Γ Γ Δ m a1 a2 a1 Γ a2 Γ Δ a2 TType τ2 mem writable Γ a2 m Γ Δ v2 τ2 mem writable Γ a1 m mem writable Γ a1 a2 v2 Γ m Proof intros Ha w2 Hw2 w1 Hw1 red unfold insertE mem insert destruct Ha as erewrite cmap lookup alter disjoint by eauto using of val flatten unshared eauto assert ctree Forall λ γ b Some Writable pbit kind γ b of val Γ tagged perm ctree flatten w2 v2 erewrite ctree flatten of val by eauto generalize val flatten Γ v2 induction Hw2 intros simpl constructor auto destruct decide addr is obj a1 erewrite cmap lookup alter by eauto eauto erewrite cmap lookup alter not obj by eauto using of val flatten unshared eauto using ctree lookup byte after Forall Qed Lemma mem dom insert Γ m a v dom indexset a v Γ m dom indexset m Proof destruct m as m simpl apply leibniz equiv dom alter Qed Locks Lemma elem of mem locks m o i o i mem locks m match cmap car m o with Some Obj w μ pbit locked ctree flatten w i Some true False end Proof destruct m as m unfold elem of lockset elem of simpl rewrite lookup omap destruct m o as w μ simplify equality try naive solver split intros ω H ω simplify option equality by rewrite list lookup fmap elem of of bools intros Hi exists of bools pbit locked ctree flatten w rewrite list lookup fmap elem of of bools in Hi by rewrite option guard True by esolve elem of Qed Lemma mem locks valid Γ m Γ Γ m Γ m mem locks m Proof intros o i rewrite elem of mem locks unfold typed index typed destruct m as m simpl rewrite lookup fmap intros Ho destruct m o as w μ eqn try done destruct cmap valid Obj Γ CMap m CMap m o w μ as τ simplify type equality auto exists τ split ands naive solver eauto using ctree typed type valid destruct ctree flatten w as eqn simplify equality erewrite ctree flatten length by eauto eauto using lookup lt Some Qed Lemma mem locks empty mem locks Proof apply dsig eq unfold mem locks simpl by rewrite omap empty Qed Lemma mem locks erase m mem locks cmap erase m mem locks m Proof destruct m as m f equal apply dsig eq simpl apply map eq intros o rewrite lookup omap by destruct m o as Qed Lemma mem unlock empty m mem unlock m m Proof destruct m as m unfold mem unlock sep unfold f equal apply map eq intros i by rewrite lookup merge lookup empty by done Qed Lemma mem lock memenv of Γ Δ m a Γ Γ Δ m mem writable Γ a m mem lock Γ a m m Proof unfold mem lock intros v by erewrite cmap alter memenv of by eauto using ctree map type of Qed Lemma mem lock forward Γ Δ m a Γ Γ Δ m mem writable Γ a m m ₘ mem lock Γ a m Proof intros by erewrite mem lock memenv of by eauto Qed Lemma mem lock valid Γ Δ m a Γ Γ Δ m mem writable Γ a m Γ Δ mem lock Γ a m Proof intros w assert Γ Δ ctree map pbit lock w type of w eapply ctree map typed eauto using cmap lookup Some pbits lock valid pbit lock indetified ctree flatten valid pbit lock mapped eapply cmap alter valid ctree Forall not eauto rewrite ctree flatten map eauto using pbits lock mapped pbits mapped pbits kind weaken Qed Lemma mem lock valid Γ m a Γ Γ m mem writable Γ a m Γ mem lock Γ a m Proof unfold valid at 2 3 cmap valid intros erewrite mem lock memenv of by eauto eauto using mem lock valid Qed Lemma mem erase lock Γ m a cmap erase mem lock Γ a m mem lock Γ a cmap erase m Proof apply cmap erase alter Qed Lemma mem lock force Γ m a dom indexset mem lock Γ a m dom indexset m Proof destruct m simpl apply leibniz equiv dom alter Qed Lemma ctree unlock typed Γ Δ w τ β s Γ Γ Δ w τ length β s bit size of Γ τ Γ Δ ctree merge pbit unlock if w β s τ Proof intros H Γ Hw revert w τ Hw β s refine ctree typed ind simpl intros typed constructor auto using pbits unlock valid intros ws τ Hws IH Hlen β s rewrite bit size of array intros H β s typed constructor auto clear Hlen IH revert β s H β s induction Hws intros f equal auto clear Hlen revert β s H β s induction Hws intros decompose Forall hyps constructor auto intros t w γ bss τ s Ht Hws IH H γ bss Hindet Hlen β s erewrite bit size of struct by eauto intros H β s typed constructor eauto clear Ht clear H γ bss Hindet revert w γ bss β s Hws IH H β s Hlen unfold field bit padding induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto constructor simpl auto clear H β s revert β s elim H γ bss intros constructor simpl auto using pbits unlock valid clear H β s revert β s elim Hindet intros constructor simpl in auto rewrite pbit indetify unlock congruence clear H γ bss IH Hindet revert w γ bss β s Hws H β s Hlen unfold field bit padding induction bit size of fields τ s H Γ intros decompose Forall hyps erewrite type of correct by eauto f equal auto intros t i τ s w γ bs τ Hc β s typed constructor eauto auto using pbits unlock valid rewrite pbit indetify unlock congruence solve length rewrite ctree flatten merge intros destruct Hc split eapply pbits unlock mapped eauto using ctree flatten valid pbits valid sep valid intros typed constructor eauto using pbits unlock valid Qed Lemma ctree unlock type of w β s type of ctree merge pbit unlock if w β s type of w Proof destruct w as τ ws f equal revert β s induction ws intros f equal auto Qed Lemma mem unlock memenv of m Ω mem unlock Ω m m Proof apply map eq intros o destruct m as m Ω as Ω simpl rewrite lookup fmap lookup merge by done destruct m o as w μ Ω o as ω simplify equality f equal by rewrite ctree unlock type of Qed Lemma mem unlock forward m Ω m ₘ mem unlock Ω m Proof by rewrite mem unlock memenv of Qed Lemma mem unlock valid Γ Δ m Ω Γ Γ Δ m Γ Δ mem unlock Ω m Proof destruct m as m Ω as Ω H Ω intros H Δ Hm1 Hm2 split ands simpl in auto intros o τ rewrite lookup merge by done intros destruct Ω o m o as eqn simplify equality eauto intros o w μ rewrite lookup merge by done intros destruct m o as w eqn Hw Ω o as ω eqn H ω simplify equality eauto destruct Hm2 o w μ as τ Hemp auto exists τ split ands auto using ctree unlock typed to bools length rewrite ctree flatten merge contradict Hemp eapply pbits unlock empty inv eauto using ctree flatten valid pbits valid sep valid Qed Lemma mem unlock valid Γ m Ω Γ Γ m Γ mem unlock Ω m Proof unfold valid at 2 3 cmap valid intros rewrite mem unlock memenv of eauto using mem unlock valid Qed Lemma mem erase unlock m Ω cmap erase mem unlock Ω m mem unlock Ω cmap erase m Proof destruct m as m Ω as Ω f equal apply map eq intros o rewrite lookup omap lookup merge lookup omap by done by destruct m o as Ω o Qed Lemma mem unlock force Ω m dom indexset mem unlock Ω m dom indexset m Proof destruct m as m Ω as Ω simpl apply elem of equiv L intros o rewrite elem of dom unfold is Some rewrite lookup merge by done destruct Ω o m o as naive solver Qed Lemma elem of lock singleton Γ a o i o i lock singleton Γ a o addr index a addr object offset Γ a i addr object offset Γ a ptr bit size of Γ type of a Proof destruct decide ptr bit size of Γ type of a 0 as Hsz split lia unfold lock singleton destruct decide as solve elem of rewrite Hsz simpl rewrite right id L apply elem of equiv empty L intros j by rewrite elem of of bools lookup replicate intros assert of bools replicate addr object offset Γ a false replicate ptr bit size of Γ type of a true rewrite elem of equiv empty L intros Hx destruct Hx addr object offset Γ a by rewrite elem of of bools lookup app r lookup replicate 2 by solve length unfold lock singleton case decide split done intros Hi simplify map equality split auto rewrite elem of of bools in Hi destruct decide i addr object offset Γ a by rewrite lookup app l lookup replicate 2 in Hi by solve length rewrite lookup app r lookup replicate in Hi by solve length destruct Hi as Hi revert Hi solve length intros eexists simplify map equality split auto by rewrite elem of of bools lookup app r lookup replicate 2 by solve length Qed Lemma elem of lock singleton typed Γ Δ a τ o i Γ Γ Δ a TType τ o i lock singleton Γ a o addr index a addr object offset Γ a i addr object offset Γ a bit size of Γ τ Proof intros rewrite elem of lock singleton by simplify type equality Qed Lemma lock singleton valid Γ Δ a τ Γ Γ Δ a TType τ addr strict Γ a Γ Δ lock singleton Γ a Proof intros o i rewrite elem of lock singleton typed by eauto intros exists addr type object a simpl split ands eauto using addr typed index addr typed type object valid eapply Nat lt le trans eapply addr object offset bit size eauto simpl lia Qed Lemma lock singleton disjoint Γ Δ a1 a2 τ1 τ2 Γ Γ Δ a1 TType τ1 addr strict Γ a1 Γ Δ a2 TType τ2 addr strict Γ a2 a1 Γ a2 lock singleton Γ a1 lock singleton Γ a2 Proof intros apply equiv empty L intros o i rewrite elem of intersection elem of lock singleton typed by eauto intros destruct addr disjoint object offset Γ Δ a1 a2 τ1 τ2 try done lia Qed Lemma mem unlock union locks Ω1 Ω2 m mem unlock Ω1 Ω2 m mem unlock Ω1 mem unlock Ω2 m Proof destruct m as m Ω1 as Ω1 Ω2 as Ω2 f equal apply map eq intros o rewrite lookup merge lookup union with lookup merge by done destruct m o as w μ Ω1 o as ω1 Ω2 o as ω2 do 2 f equal auto by rewrite commutative L ctree flatten merge zip with length l eq ctree merge merge pbit unlock if orb to bools union by auto using to bools length pbits unlock orb Qed Lemma mem locks alloc Γ Δ m o μ γ v τ Γ Γ Δ v τ perm locked γ false o dom indexset m mem locks mem alloc Γ o μ γ v m mem locks m Proof rewrite cmap dom alt intros apply elem of equiv L intros o i rewrite elem of mem locks destruct m as m simplify type equality destruct decide o o simplify map equality split try done erewrite ctree flatten of val by eauto unfold pbit locked rewrite list lookup fmap list fmap compose fmap zip with l list lookup fmap fmap Some by auto setoid rewrite lookup replicate intros congruence Qed Lemma mem locks alloc list Γ Δ m vs os τ s Γ Forall fresh dom indexset m os length os length vs Γ Δ vs τ s mem locks mem alloc list Γ os vs m mem locks m Proof rewrite Forall2 same length intros Hos Hovs Hvs revert os m Hos Hovs induction Hvs as v τ vs τ s IH intros m o os decompose Forall hyps auto assert o dom indexset mem alloc list Γ os vs m rewrite mem dom alloc list by eauto using Forall2 length esolve elem of by erewrite mem locks alloc IH by eauto Qed Lemma mem locks free m o μ mem freeable perm o μ m mem locks mem free o m mem locks m Proof intros w Hperm apply elem of equiv L intros o i rewrite elem of mem locks destruct m as m simplify equality destruct decide o o simplify map equality split try done rewrite fmap Some intros x b decompose Forall hyps Qed Lemma mem locks alter ref Γ Δ g o r m w τ σ o i Γ Γ Δ

    Original URL path: http://robbertkrebbers.nl/research/ch2o/memory.html (2015-08-10)
    Open archived version from archive

  • Module memory_refine
    τ4 eauto using mem alloc forward memenv forward typed mem alloc index typed inv intros o3 o4 r τ4 Ho4 destruct decide o1 o3 as destruct Ho4 simplify map equality setoid rewrite ref typed nil eauto using mem alloc index typed destruct meminj injective ne f o1 o2 o3 o4 r as simplify map equality eauto using memenv refine injective destruct memenv refine typed r H Δ o3 o4 r τ4 as τ3 eauto using mem alloc forward memenv forward typed mem alloc index typed inv by destruct ref disjoint nil inv l r intros o3 o4 r destruct decide o1 o3 as simplify equality eauto using mem alloc index alive destruct meminj injective ne f o1 o2 o3 o4 r as eauto using memenv refine injective mem alloc index alive ne mem alloc index alive inv memenv refine alive l by destruct ref disjoint nil inv l r intros o3 o4 r destruct decide o2 o4 as destruct memenv refine injective Γ α f Δ1 Δ2 H Δ o1 o3 o4 r simplify equality eauto using mem alloc index alive by destruct ref disjoint nil inv l r eauto using mem alloc index alive ne mem alloc index alive inv memenv refine alive r with congruence intros o3 destruct decide o1 o3 as eauto eauto using memenv refine perm l mem alloc index typed inv intros o4 destruct decide o2 o4 as eauto eauto using memenv refine perm r mem alloc index typed inv Qed Lemma mem alloc refine Γ α f Δ1 Δ2 m1 m2 o1 o2 mallc x v1 v2 τ let Δ1 o1 τ false Δ1 in let Δ2 o2 τ false Δ2 in Γ m1 Γ α f Δ1 Δ2 m2 Δ1 o1 None Δ2 o2 None f o1 Some o2 sep unshared x v1 Γ α f Δ1 Δ2 v2 τ mem alloc Γ o1 mallc x v1 m1 Γ α f Δ1 Δ2 mem alloc Γ o2 mallc x v2 m2 Proof simpl intros H Δ Hm assert sep valid x by by apply sep unshared valid split split ands eauto 5 using mem alloc valid mem alloc refine env val refine typed l val refine typed r sep unshared unmapped destruct m1 as m1 m2 as m2 intros o3 o4 r w3 μ simpl in rewrite lookup insert Some intros simplify map equality exists of val Γ replicate bit size of Γ τ x v2 of val Γ replicate bit size of Γ τ x v2 τ erewrite val refine type of r val refine type of l by eauto auto 7 using of val refine Forall replicate destruct meminj injective ne f o1 o2 o3 o4 r as simplify map equality eauto using memenv refine injective destruct Hm o3 o4 r w3 μ as w2 w2 τ2 auto exists w2 w2 τ2 eauto 10 using ctree refine weaken mem alloc forward mem alloc refine env meminj extend reflexive by destruct ref disjoint nil inv l r Qed Lemma mem alloc refine Γ α f m1 m2 o1 o2 μ x v1 v2 τ Γ m1 Γ α f m2 o1 dom indexset m1 o2 dom indexset m2 sep unshared x v1 Γ α f m1 m2 v2 τ f 1 f o1 Some o2 2 mem alloc Γ o1 μ x v1 m1 Γ α f mem alloc Γ o2 μ x v2 m2 3 meminj extend f f m1 m2 Proof intros Hv destruct mem refine extend Γ α f m1 m2 o1 o2 as f eauto using mem allocable memenv of cmap refine memenv refine exists f split ands auto unfold refineM cmap refine erewrite mem alloc memenv of by eauto using val refine typed l val refine typed r eapply mem alloc refine eauto 10 using mem allocable memenv of cmap refine weaken val refine weaken mem alloc forward mem alloc refine env Qed Lemma mem alloc new refine Γ α f m1 m2 o1 o2 μ x τ Γ m1 Γ α f m2 o1 dom indexset m1 o2 dom indexset m2 sep unshared x Γ τ f 1 f o1 Some o2 2 mem alloc Γ o1 μ x val new Γ τ m1 Γ α f mem alloc Γ o2 μ x val new Γ τ m2 3 meminj extend f f m1 m2 Proof eauto using mem alloc refine val new refine Qed Hint Immediate cmap refine valid l cmap refine valid r Hint Immediate cmap refine memenv refine Lemma mem alloc list refine Γ α f m1 m2 os1 os2 vs1 vs2 τ s Γ m1 Γ α f m2 vs1 Γ α f m1 m2 vs2 τ s length os1 length vs1 length os2 length vs2 Forall fresh dom indexset m1 os1 Forall fresh dom indexset m2 os2 f 1 Forall2 λ o1 o2 f o1 Some o2 os1 os2 2 mem alloc list Γ os1 vs1 m1 Γ α f mem alloc list Γ os2 vs2 m2 3 meminj extend f f m1 m2 Proof rewrite Forall2 same length intros Hm Hvs Hovs1 Hovs2 Hos1 Hos2 revert τ s os2 vs2 Hos1 Hos2 Hvs Hovs2 induction Hovs1 as o1 v1 os1 vs1 IH intros τ τ s o2 os2 v2 vs2 inversion clear 1 inversion clear 1 inversion clear 1 intros decompose Forall hyps eauto using meminj extend reflexive assert Γ m1 v1 τ by eauto using val refine typed l assert Γ m2 v2 τ by eauto using val refine typed r assert Γ τ by eauto using val typed type valid destruct IH τ s os2 vs2 as f auto assert o1 dom indexset mem alloc list Γ os1 vs1 m1 rewrite mem dom alloc list elem of union elem of of list by eauto using Forall2 length tauto assert o2 dom indexset mem alloc list Γ os2 vs2 m2 rewrite mem dom alloc list elem of union elem of of list by eauto using Forall2 length tauto destruct mem alloc refine Γ α f mem alloc list Γ os1 vs1 m1 mem alloc list Γ os2 vs2 m2 o1 o2 false perm full v1 v2 τ as f eauto 6 using perm full mapped perm full unshared val refine weaken mem alloc list forward exists f split ands eauto using meminj extend transitive assert mem alloc list Γ os1 vs1 m1 os1 τ s by eauto using mem alloc list index typed constructor auto decompose Forall eapply transitivity with f eauto using eq sym meminj extend left eapply meminj extend transitive eauto using mem alloc list forward Qed Lemma mem freeable refine Γ α f Δ1 Δ2 m1 m2 a1 a2 τ p Γ m1 Γ α f Δ1 Δ2 m2 a1 Γ α f Δ1 Δ2 a2 τ p mem freeable a1 m1 mem freeable a2 m2 Proof intros Hm Ha w1 rewrite addr is top array alt in Ha by eauto using addr refine typed l destruct Ha as τ n Ha1 destruct addr ref refine Γ α f Δ1 Δ2 a1 a2 τ p as r Ha2 eauto destruct Hm addr index a1 addr index a2 r w1 true as w2 τ Hr auto specialize Hr I simplify type equality split exists w2 eauto using pbits refine perm 1 ctree flatten refine rewrite addr is top array alt by eauto using addr refine typed r assert addr ref Γ a2 RArray 0 τ n as by rewrite Ha1 in Ha2 inversion Ha2 as Harr inversion Harr decompose Forall hyps erewrite addr ref byte refine by eauto exists τ n split ands eauto using addr strict refine Qed Lemma mem freeable index refine Γ α f Δ1 Δ2 m1 m2 a1 a2 τ p Γ m1 Γ α f Δ1 Δ2 m2 a1 Γ α f Δ1 Δ2 a2 τ p mem freeable a1 m1 f addr index a1 Some addr index a2 Proof intros Hm Ha w1 rewrite addr is top array alt in Ha by eauto using addr refine typed l destruct Ha as τ n Ha1 addr ref refine Γ α f Δ1 Δ2 a1 a2 τ p as r Ha2 naive solver Qed Lemma mem free refine env Γ α f Δ1 Δ2 o1 o2 Δ1 Γ α f Δ2 f o1 Some o2 alter prod map id λ true o1 Δ1 Γ α f alter prod map id λ true o2 Δ2 Proof intros H Δ split eauto using memenv refine injective eauto using memenv refine frozen intros o3 o4 r τ3 destruct memenv refine typed l H Δ o3 o4 r τ3 as τ4 eauto using mem free index typed inv mem free forward memenv forward typed intros o3 o4 r τ4 destruct memenv refine typed r H Δ o3 o4 r τ4 as τ3 eauto using mem free index typed inv mem free forward memenv forward typed intros o3 o4 r destruct decide o2 o4 as destruct memenv refine injective Γ α f Δ1 Δ2 H Δ o1 o3 o4 r simplify equality eauto by destruct mem free index alive Δ1 o3 by destruct ref disjoint nil inv l r eauto using mem free index alive ne mem free index alive inv memenv refine alive l intros o3 o4 r destruct decide o1 o3 simplify equality by destruct mem free index alive Δ2 o4 eauto using mem free index alive ne mem free index alive inv memenv refine alive r intros o3 τ destruct decide o1 o3 as eauto eauto using memenv refine perm l mem free index typed inv intros o4 τ destruct decide o2 o4 as eauto eauto using memenv refine perm r mem free index typed inv Qed Lemma mem free refine env l Γ f Δ1 Δ2 o Δ1 Γ true f Δ2 alter prod map id λ true o Δ1 Γ true f Δ2 Proof destruct 1 split simpl try by auto eauto using mem free index typed inv naive solver eauto using mem free forward memenv forward typed eauto using mem free index alive inv Qed Lemma mem free refine env r Γ f Δ1 Δ2 o Δ1 Γ true f Δ2 o r f o Some o r index alive Δ1 o Δ1 Γ true f alter prod map id λ true o Δ2 Proof intros Hf split simpl try by auto naive solver eauto using mem free forward memenv forward typed eauto using mem free index typed inv intros o1 o2 r destruct decide o2 o as by destruct Hf o1 r eauto using mem free index alive ne Qed Lemma mem free refine Γ α f Δ1 Δ2 m1 m2 o1 o2 let Δ1 alter prod map id λ true o1 Δ1 in let Δ2 alter prod map id λ true o2 Δ2 in Γ m1 Γ α f Δ1 Δ2 m2 f o1 Some o2 mem free o1 m1 Γ α f Δ1 Δ2 mem free o2 m2 Proof simpl intros Hm split split ands auto using mem free valid mem free refine env destruct m1 as m1 m2 as m2 simpl in intros o1 o2 r w1 μ rewrite lookup alter Some intros simplify equality eauto destruct Hm o1 o2 r w1 μ as w2 w2 τ2 auto destruct decide o2 o2 as simplify map equality destruct meminj injective alt f o1 o1 o2 r as simplify map equality eauto using memenv refine injective by destruct ref disjoint nil inv l r exists w2 w2 τ2 split ands eauto using ctree refine weaken mem free forward mem free refine env meminj extend reflexive Qed Lemma mem free refine l Γ f Δ1 Δ2 m1 m2 o let Δ1 alter prod map id λ true o Δ1 in Γ m1 Γ true f Δ1 Δ2 m2 mem free o m1 Γ true f Δ1 Δ2 m2 Proof simpl intros Hm split split ands auto using mem free valid mem free refine env l destruct m1 as m1 m2 as m2 simpl in intros o1 o2 r w1 μ rewrite lookup alter Some intros simplify equality eauto destruct Hm o1 o2 r w1 μ as w2 w2 τ2 auto exists w2 w2 τ2 eauto 10 using ctree refine weaken mem free forward mem free refine env l meminj extend reflexive Qed Lemma mem free refine r Γ f Δ1 Δ2 m1 m2 o let Δ2 alter prod map id λ true o Δ2 in Γ o r f o Some o r index alive Δ1 o m1 Γ true f Δ1 Δ2 m2 m1 Γ true f Δ1 Δ2 mem free o m2 Proof simpl intros Hf Hm1 Hm split split ands auto using mem free valid mem free refine env r destruct m1 as m1 m2 as m2 simpl in intros o1 o2 r w1 μ destruct cmap valid Obj Γ Δ1 CMap m1 o1 w1 μ as τ1 auto destruct decide o2 o as by destruct Hf o1 r destruct Hm o1 o2 r w1 μ as w2 w2 τ2 auto exists w2 w2 τ2 simplify map equality eauto 7 using ctree refine weaken mem free forward mem free refine env r meminj extend reflexive Qed Lemma mem free refine Γ α f m1 m2 o1 o2 Γ m1 Γ α f m2 f o1 Some o2 mem free o1 m1 Γ α f mem free o2 m2 Proof unfold refineM cmap refine rewrite mem free memenv of eauto using mem free refine Qed Lemma mem foldr free refine Γ α f m1 m2 os1 os2 Γ m1 Γ α f m2 Forall2 λ o1 o2 f o1 Some o2 os1 os2 foldr mem free m1 os1 Γ α f foldr mem free m2 os2 Proof induction 3 simpl auto using mem free refine Qed Lemma locks refine id Γ α Δ Ω Γ Δ Ω Ω Γ α Δ Ω Proof split split ands intros until 0 rewrite lookup meminj id intros simplify type equality eauto using memenv refine id Qed Lemma locks refine compose Γ α1 α2 f1 f2 Δ1 Δ2 Δ3 Ω1 Ω2 Ω3 Γ Ω1 Γ α1 f1 Δ1 Δ2 Ω2 Ω2 Γ α2 f2 Δ2 Δ3 Ω3 Ω1 Γ α1 α2 f2 f1 Δ1 Δ3 Ω3 Proof intros H Δ12 H Ω12 H Δ23 H Ω23 split split ands eauto using memenv refine compose intros o1 o3 r τ1 i rewrite lookup meminj compose Some intros o2 r2 r3 destruct memenv refine typed l H Δ12 o1 o2 r2 τ1 as τ2 auto destruct memenv refine typed l H Δ23 o2 o3 r3 τ2 as τ3 auto assert ref object offset Γ r2 i bit size of Γ τ2 apply Nat lt le trans with ref object offset Γ r2 bit size of Γ τ1 lia eauto using ref object offset size rewrite H Ω12 H Ω23 by eauto using memenv refine alive l by rewrite ref object offset app Nat add assoc Nat add comm ref object offset Γ r2 Qed Lemma locks refine inverse Γ f Δ1 Δ2 Ω1 Ω2 Ω1 Γ false f Δ1 Δ2 Ω2 Ω2 Γ false meminj inverse f Δ2 Δ1 Ω1 Proof intros Hf split split ands eauto using memenv refine inverse intros o2 o1 r τ i Ho2 destruct lookup meminj inverse 1 Γ f Δ1 Δ2 o1 o2 r τ as simpl auto symmetry apply Hf τ eauto using memenv refine alive r Qed Lemma locks refine valid l Γ α f Δ1 Δ2 Ω1 Ω2 Ω1 Γ α f Δ1 Δ2 Ω2 Γ Δ1 Ω1 Proof by intros Qed Lemma locks list refine valid l Γ α f Δ1 Δ2 Ω s1 Ω s2 Ω s1 Γ α f Δ1 Δ2 Ω s2 Γ Δ1 Ω s1 Proof induction 1 eauto using locks refine valid l Qed Lemma locks refine valid r Γ α f Δ1 Δ2 Ω1 Ω2 Ω1 Γ α f Δ1 Δ2 Ω2 Γ Δ2 Ω2 Proof by intros Qed Lemma locks list refine valid r Γ α f Δ1 Δ2 Ω s1 Ω s2 Ω s1 Γ α f Δ1 Δ2 Ω s2 Γ Δ2 Ω s2 Proof induction 1 eauto using locks refine valid r Qed Lemma locks refine weaken Γ α α f f Δ1 Δ2 Δ1 Δ2 Ω1 Ω2 Γ Ω1 Γ α f Δ1 Δ2 Ω2 Δ1 Γ α f Δ2 Δ1 ₘ Δ1 Δ2 ₘ Δ2 meminj extend f f Δ1 Δ2 Ω1 Γ α f Δ1 Δ2 Ω2 Proof intros H Ω1 H Ω2 H Δ12 H Ω H Δ split split ands eauto 2 using lockset valid weaken intros o1 o2 r τ1 i split intros destruct H Ω1 o1 i as τ1 auto assert τ1 τ1 by eauto using typed unique memenv forward typed simplify type equality by erewrite H Ω by eauto using memenv forward alive option eq 1 intros destruct H Ω2 o2 ref object offset Γ r i as τ2 auto destruct memenv refine typed r H Δ12 o1 o2 r τ2 as τ1 eauto assert τ1 τ1 by eauto using typed unique memenv forward typed simplify type equality by erewrite H Ω by eauto using memenv forward alive Qed Lemma locks empty refine Γ α f Δ1 Δ2 Δ1 Γ α f Δ2 lockset Γ α f Δ1 Δ2 Proof split split ands eauto using lockset empty valid solve elem of Qed Lemma mem locks refine Γ α f m1 m2 Γ m1 Γ α f m2 mem locks m1 Γ α f m1 m2 mem locks m2 Proof intros Hm1 Hm2 Hm split split ands auto using mem locks valid intros o1 o2 r σ1 i σ1 assert w1 μ cmap car m1 o1 Some Obj w1 μ as w1 μ destruct m1 as m1 simplify map equality destruct m1 o1 as naive solver destruct Hm o1 o2 r w1 μ as w2 w2 τ2 auto clear Hm assert Γ m1 w1 τ2 by eauto destruct cmap valid Obj Γ m1 m1 o1 w1 μ as cmap valid Obj Γ m2 m2 o2 w2 μ as τ simplify type equality auto rewrite elem of mem locks

    Original URL path: http://robbertkrebbers.nl/research/ch2o/memory_refine.html (2015-08-10)
    Open archived version from archive

  • Module memory_separation
    Forall not cmap lookup Some pbits mapped pbits kind weaken exists w2 eauto using pbits kind subseteq ctree flatten subseteq Qed Lemma mem insert disjoint Γ Δ1 m1 m2 a1 v1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a1 TType τ1 mem writable Γ a1 m1 Γ Δ1 v1 τ1 a1 v1 Γ m1 m2 Proof intros w1 assert ctree unshared w1 eapply pbits unshared eauto using pbits kind weaken pbits valid sep valid ctree flatten valid assert ctree Forall not sep unmapped w1 eapply pbits mapped eauto using pbits kind weaken eapply cmap alter disjoint eauto using of val flatten typed of val flatten mapped of val flatten disjoint ctree Forall not Qed Lemma mem insert disjoint le Γ Δ m ms a v τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m Γ Δ v τ m ms a v Γ m ms Proof intros apply sep disjoint cons le inj intros m rewrite sep disjoint list double symmetry iff m eauto using mem insert disjoint Qed Lemma mem insert union Γ Δ1 m1 m2 a1 v1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a1 TType τ1 mem writable Γ a1 m1 Γ Δ1 v1 τ1 a1 v1 Γ m1 m2 a1 v1 Γ m1 m2 Proof intros w1 assert ctree unshared w1 eapply pbits unshared eauto using pbits kind weaken pbits valid sep valid ctree flatten valid assert ctree Forall not sep unmapped w1 eapply pbits mapped eauto using pbits kind weaken eapply cmap alter union eauto using of val flatten typed ctree Forall not of val flatten mapped of val flatten disjoint of val flatten union Qed Lemma mem lock disjoint Γ Δ1 m1 m2 a1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a1 TType τ1 mem writable Γ a1 m1 mem lock Γ a1 m1 m2 Proof intros w1 Hw1 assert Γ Δ1 ctree map pbit lock w1 τ1 eapply ctree map typed eauto using cmap lookup Some pbits lock valid pbit lock indetified ctree flatten valid pbit lock mapped eapply cmap alter disjoint eauto eapply ctree Forall not eauto rewrite ctree flatten map apply Forall fmap apply Forall impl not sep unmapped eauto using pbits mapped pbits kind weaken pbit lock mapped eauto 8 using ctree map disjoint ctree flatten disjoint Forall true pbit lock mapped Forall impl pbit lock unmapped pbits lock disjoint Qed Lemma mem lock disjoint le Γ Δ m ms a τ Γ Γ Δ m Γ Δ a TType τ mem writable Γ a m m ms mem lock Γ a m ms Proof intros apply sep disjoint cons le inj intros m rewrite sep disjoint list double symmetry iff m eauto using mem lock disjoint Qed Lemma mem lock union Γ Δ1 m1 m2 a1 τ1 Γ Γ Δ1 m1 m1 m2 Γ Δ1 a1 TType τ1 mem writable Γ a1 m1 mem lock Γ a1 m1 m2 mem lock Γ a1 m1 m2 Proof intros

    Original URL path: http://robbertkrebbers.nl/research/ch2o/memory_separation.html (2015-08-10)
    Open archived version from archive

  • Module aliasing
    j r j r s r1 i1 r2 i2 r auto clear IH simplify equality left intros j1 j2 apply ref disjoint cons l ref disjoint cons r by rewrite ref set offset offset r1 ref set offset offset r2 rewrite ref typed app in Hr1 destruct Hr1 as τ2 Hr2 Hr assert τ2 τ2 as by eauto using ref set offset typed unique eq sym destruct ref set offset disjoint r2 j as left intros j1 j2 rewrite app comm cons by apply ref disjoint app l ref disjoint cons r destruct aux τ2 rs2 rs1 r σ2 σ1 as Hr j r Hr s i1 r2 i2 Hr2 simplify equality auto econstructor eauto destruct app injective 1 freeze true r r freeze true ref set offset j r2 ref set offset j r2 rewrite fmap length fmap app congruence left intros j1 j2 rewrite app comm cons apply ref disjoint here app symmetry Hr right left exists j r by rewrite app comm cons Hr associative L do 3 right eexists s r2 i2 i1 r2 by rewrite app comm cons Hr2 associative L rewrite ref typed app in Hr2 destruct Hr2 as τ1 Hr1 Hr assert τ1 τ1 as by eauto using ref set offset typed unique eq sym destruct ref set offset disjoint r1 j as simpl left intros rewrite app comm cons by apply ref disjoint app destruct aux τ1 rs1 rs2 r σ1 σ2 as Hr j r Hr s i1 r2 i2 Hr1 simplify equality auto econstructor eauto destruct app injective 1 freeze true r r freeze true ref set offset j r1 ref set offset j r1 rewrite fmap length fmap app congruence left intros j1 j2 rewrite app comm cons apply ref disjoint here app Hr do 2 right left exists j r by rewrite app comm cons Hr associative L do 3 right eexists s i1 r2 i2 r1 by rewrite app comm cons Hr1 associative L by do 3 right eexists s rs1 r1 i1 rs2 r2 i2 r Qed Lemma addr disjoint cases Γ Δ a1 a2 σ1 σ2 Γ Γ Δ a1 TType σ1 frozen a1 σ1 ucharT T Γ Δ a2 TType σ2 frozen a2 σ2 ucharT T 1 j1 j2 addr plus Γ j1 a1 Γ addr plus Γ j2 a2 2 σ1 Γ σ2 3 σ2 Γ σ1 4 addr index a1 addr index a2 t r1 i1 r2 i2 r addr ref base a1 r1 RUnion i1 t true r addr ref base a2 r2 RUnion i2 t true r i1 i2 Proof unfold frozen intros Ha1 Ha2 assert addr is obj a1 addr is obj a2 as split apply dec stable intuition eauto using addr not is obj type inversion Ha1 as o1 r1 i1 τ1 σ p1 inversion Ha2 as o2 r2 i2 τ2 σ p2 intros simplify equality destruct decide o1 o2 simplify type equality by do 2 left destruct ref disjoint cases Γ τ2 r1 r2 σ p1 σ

    Original URL path: http://robbertkrebbers.nl/research/ch2o/aliasing.html (2015-08-10)
    Open archived version from archive

  • Module constant_propagation
    tagged perm ctree flatten w v erewrite ctree flatten of val by rewrite fmap length eauto using ctree flatten length cmap lookup typed generalize val flatten Γ v induction Hw intros simpl constructor auto destruct cmap lookup alter refine Γ Δ λ w of val Γ tagged perm ctree flatten w v m a w τ as w simpl eauto using of val flatten typed cmap lookup typed of val

    Original URL path: http://robbertkrebbers.nl/research/ch2o/constant_propagation.html (2015-08-10)
    Open archived version from archive

  • Module assignments
    v assign sem Γ m a v PreOp op v v PostOp sem op va v m Γ a Some va val binop ok Γ m op va v val cast ok Γ m type of a val binop Γ op va v v val cast type of a val binop Γ op va v assign sem Γ m a v PostOp op v va Inductive assign typed Env K τ1 type K type K assign Prop Assign typed τ2 cast typed τ2 τ1 assign typed τ1 τ2 Assign PreOp typed op τ2 σ binop typed op τ1 τ2 σ cast typed σ τ1 assign typed τ1 τ2 PreOp op PostOp typed op τ2 σ binop typed op τ1 τ2 σ cast typed σ τ1 assign typed τ1 τ2 PostOp op Section assignments Context EnvSpec K Lemma assign typed type valid Γ ass τ1 τ2 assign typed τ1 τ2 ass Γ TType τ1 Γ τ2 Γ τ1 Proof destruct 1 eauto using cast typed type valid binop typed type valid type valid ptr type valid Qed Lemma assign sem erase Γ m a v ass va v assign sem Γ cmap erase m a v ass va v assign sem Γ m a v ass va v Proof split destruct 1 econstructor rewrite 1 val binop ok erase 1 val cast ok erase 1 mem lookup erase eauto destruct 1 econstructor rewrite val binop ok erase val cast ok erase mem lookup erase eauto Qed Lemma assign sem deterministic Γ m a v ass va1 va2 v1 v2 assign sem Γ m a v ass va1 v1 assign sem Γ m a v ass va2 v2 va1 va2 v1 v2 Proof by destruct 1 inversion 1 simplify option equality Qed Lemma assign preservation Γ Δ m ass a v va

    Original URL path: http://robbertkrebbers.nl/research/ch2o/assignments.html (2015-08-10)
    Open archived version from archive