theory Schedule_R

lemma tcbSchedDequeue_valid_queues_weak:
  "\<lbrace> valid_queues_no_bitmap_except t and valid_bitmapQ and
     bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and
     correct_queue t and
     obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t \<rbrace>
   tcbSchedDequeue t
   \<lbrace>\<lambda>_. Invariants_H.valid_queues\<rbrace>" proof - show ?thesis unfolding tcbSchedDequeue_def null_def valid_queues_def apply wp  (* stops on threadSet *)
           apply (rule hoare_post_eq[OF _ threadSet_valid_queues_dequeue_wp],
                 simp add: valid_queues_def) apply (wp hoare_vcg_if_lift hoare_vcg_conj_lift hoare_vcg_imp_lift)+ apply (wp hoare_vcg_imp_lift setQueue_valid_queues_no_bitmap_except_dequeue_wp
                       setQueue_valid_bitmapQ threadGet_const_tcb_at hoare_vcg_if_lift)+ 
  (* wp done *)
   apply (normalise_obj_at') apply (clarsimp simp: correct_queue_def) apply (normalise_obj_at') apply (fastforce simp add: valid_queues_no_bitmap_except_def valid_queues_no_bitmap_def elim: obj_at'_weaken)+ done qed

(* Proof state trace *)
proof (prove)
goal (1 subgoal):
 1. \<lbrace>valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t\<rbrace> tcbSchedDequeue t \<lbrace>\<lambda>_. Invariants_H.valid_queues\<rbrace> proof (state)
goal (1 subgoal):
 1. \<lbrace>valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t\<rbrace> tcbSchedDequeue t \<lbrace>\<lambda>_. Invariants_H.valid_queues\<rbrace> proof (prove)
goal (1 subgoal):
 1. \<lbrace>valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t\<rbrace> tcbSchedDequeue t \<lbrace>\<lambda>_. Invariants_H.valid_queues\<rbrace> proof (prove)
goal (1 subgoal):
 1. \<lbrace>valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t\<rbrace> do queued <- threadGet tcbQueued t;
when queued $ do tdom <- threadGet tcbDomain t;
prio <- threadGet tcbPriority t;
queue <- getQueue tdom prio;
queue' <- return (filter (\<lambda>x. x \<noteq> t) queue);
setQueue tdom prio queue';
when (queue' = []) $ removeFromBitmap tdom prio;
threadSet (tcbQueued_update (\<lambda>_. False)) t
od
od \<lbrace>\<lambda>_ s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s\<rbrace> proof (prove)
goal (9 subgoals):
 1. \<And>queued tdom prio queue queue' x xa. queued \<Longrightarrow> \<lbrace>?B10 queued tdom prio queue queue' x xa\<rbrace> threadSet (tcbQueued_update (\<lambda>_. False)) t \<lbrace>\<lambda>_ s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s\<rbrace>
 2. \<And>queued tdom prio queue queue' x. queued \<Longrightarrow> \<lbrace>?B8 queued tdom prio queue queue' x\<rbrace> when (queue' = []) $ removeFromBitmap tdom prio \<lbrace>?B10 queued tdom prio queue queue' x\<rbrace>
 3. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?B7 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>?B8 queued tdom prio queue queue'\<rbrace>
 4. \<And>queued tdom prio queue. queued \<Longrightarrow> \<lbrace>?B6 queued tdom prio queue\<rbrace> return (filter (\<lambda>x. x \<noteq> t) queue) \<lbrace>?B7 queued tdom prio queue\<rbrace>
 5. \<And>queued tdom prio. queued \<Longrightarrow> \<lbrace>?B5 queued tdom prio\<rbrace> getQueue tdom prio \<lbrace>?B6 queued tdom prio\<rbrace>
 6. \<And>queued tdom. queued \<Longrightarrow> \<lbrace>?B4 queued tdom\<rbrace> threadGet tcbPriority t \<lbrace>?B5 queued tdom\<rbrace>
 7. \<And>queued. queued \<Longrightarrow> \<lbrace>?Q3 queued\<rbrace> threadGet tcbDomain t \<lbrace>?B4 queued\<rbrace>
 8. \<lbrace>?Q\<rbrace> threadGet tcbQueued t \<lbrace>\<lambda>queued. if queued then ?Q3 queued else (\<lambda>s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s)\<rbrace>
 9. \<And>s. (valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t) s \<Longrightarrow> ?Q s proof (prove)
goal (9 subgoals):
 1. \<And>queued tdom prio queue queue' x xa. queued \<Longrightarrow> \<lbrace>?B10 queued tdom prio queue queue' x xa\<rbrace> threadSet (tcbQueued_update (\<lambda>_. False)) t \<lbrace>\<lambda>_ s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s\<rbrace>
 2. \<And>queued tdom prio queue queue' x. queued \<Longrightarrow> \<lbrace>?B8 queued tdom prio queue queue' x\<rbrace> when (queue' = []) $ removeFromBitmap tdom prio \<lbrace>?B10 queued tdom prio queue queue' x\<rbrace>
 3. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?B7 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>?B8 queued tdom prio queue queue'\<rbrace>
 4. \<And>queued tdom prio queue. queued \<Longrightarrow> \<lbrace>?B6 queued tdom prio queue\<rbrace> return (filter (\<lambda>x. x \<noteq> t) queue) \<lbrace>?B7 queued tdom prio queue\<rbrace>
 5. \<And>queued tdom prio. queued \<Longrightarrow> \<lbrace>?B5 queued tdom prio\<rbrace> getQueue tdom prio \<lbrace>?B6 queued tdom prio\<rbrace>
 6. \<And>queued tdom. queued \<Longrightarrow> \<lbrace>?B4 queued tdom\<rbrace> threadGet tcbPriority t \<lbrace>?B5 queued tdom\<rbrace>
 7. \<And>queued. queued \<Longrightarrow> \<lbrace>?Q3 queued\<rbrace> threadGet tcbDomain t \<lbrace>?B4 queued\<rbrace>
 8. \<lbrace>?Q\<rbrace> threadGet tcbQueued t \<lbrace>\<lambda>queued. if queued then ?Q3 queued else (\<lambda>s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s)\<rbrace>
 9. \<And>s. (valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t) s \<Longrightarrow> ?Q s proof (prove)
goal (8 subgoals):
 1. \<And>queued tdom prio queue queue' x. queued \<Longrightarrow> \<lbrace>?B8 queued tdom prio queue queue' x\<rbrace> when (queue' = []) $ removeFromBitmap tdom prio \<lbrace>\<lambda>xa. valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and (\<lambda>s. \<forall>d p. t \<notin> set (ksReadyQueues s (d, p)))\<rbrace>
 2. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?B7 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>?B8 queued tdom prio queue queue'\<rbrace>
 3. \<And>queued tdom prio queue. queued \<Longrightarrow> \<lbrace>?B6 queued tdom prio queue\<rbrace> return (filter (\<lambda>x. x \<noteq> t) queue) \<lbrace>?B7 queued tdom prio queue\<rbrace>
 4. \<And>queued tdom prio. queued \<Longrightarrow> \<lbrace>?B5 queued tdom prio\<rbrace> getQueue tdom prio \<lbrace>?B6 queued tdom prio\<rbrace>
 5. \<And>queued tdom. queued \<Longrightarrow> \<lbrace>?B4 queued tdom\<rbrace> threadGet tcbPriority t \<lbrace>?B5 queued tdom\<rbrace>
 6. \<And>queued. queued \<Longrightarrow> \<lbrace>?Q3 queued\<rbrace> threadGet tcbDomain t \<lbrace>?B4 queued\<rbrace>
 7. \<lbrace>?Q\<rbrace> threadGet tcbQueued t \<lbrace>\<lambda>queued. if queued then ?Q3 queued else (\<lambda>s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s)\<rbrace>
 8. \<And>s. (valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t) s \<Longrightarrow> ?Q s proof (prove)
goal (12 subgoals):
 1. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?Q'45 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv. valid_queues_no_bitmap_except t\<rbrace>
 2. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?P'44 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv s. queue' \<noteq> [] \<longrightarrow> valid_queues_no_bitmap_except t s\<rbrace>
 3. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?P'42 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv. if queue' = [] then valid_bitmapQ_except tdom prio and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and (\<lambda>s. ksReadyQueues s (tdom, prio) = []) else valid_bitmapQ\<rbrace>
 4. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?P'41 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv. if queue' = [] then bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans else bitmapQ_no_L2_orphans\<rbrace>
 5. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?P'40 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv. if queue' = [] then bitmapQ_no_L1_orphans else bitmapQ_no_L1_orphans\<rbrace>
 6. \<And>queued tdom prio queue queue'. queued \<Longrightarrow> \<lbrace>?P'39 queued tdom prio queue queue'\<rbrace> setQueue tdom prio queue' \<lbrace>\<lambda>rv. if queue' = [] then \<lambda>s. \<forall>d p. t \<notin> set (ksReadyQueues s (d, p)) else (\<lambda>s. \<forall>d p. t \<notin> set (ksReadyQueues s (d, p)))\<rbrace>
 7. \<And>queued tdom prio queue. queued \<Longrightarrow> \<lbrace>?B6 queued tdom prio queue\<rbrace> return (filter (\<lambda>x. x \<noteq> t) queue) \<lbrace>\<lambda>queue' s. (((((queue' \<noteq> [] \<or> ?Q'45 queued tdom prio queue queue' s) \<and> ?P'44 queued tdom prio queue queue' s) \<and> ?P'42 queued tdom prio queue queue' s) \<and> ?P'41 queued tdom prio queue queue' s) \<and> ?P'40 queued tdom prio queue queue' s) \<and> ?P'39 queued tdom prio queue queue' s\<rbrace>
 8. \<And>queued tdom prio. queued \<Longrightarrow> \<lbrace>?B5 queued tdom prio\<rbrace> getQueue tdom prio \<lbrace>?B6 queued tdom prio\<rbrace>
 9. \<And>queued tdom. queued \<Longrightarrow> \<lbrace>?B4 queued tdom\<rbrace> threadGet tcbPriority t \<lbrace>?B5 queued tdom\<rbrace>
 10. \<And>queued. queued \<Longrightarrow> \<lbrace>?Q3 queued\<rbrace> threadGet tcbDomain t \<lbrace>?B4 queued\<rbrace>
A total of 12 subgoals... proof (prove)
goal (1 subgoal):
 1. \<And>s. (valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t) s \<Longrightarrow> tcb_at' t s \<and> obj_at' ((\<lambda>rv. (if rv then \<lambda>s. tcb_at' t s \<and> obj_at' ((\<lambda>rv. tcb_at' t s \<and> obj_at' ((\<lambda>rva. (((((filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_queues_no_bitmap_except t s \<and> (\<forall>t'\<in>set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))). obj_at' (inQ rv rva and runnable' \<circ> tcbState) t' s) \<and> t \<notin> set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> rva \<le> maxPriority \<and> rv \<le> maxDomain) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_queues_no_bitmap_except t s \<and> (\<forall>t'\<in>set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))). obj_at' (inQ rv rva and runnable' \<circ> tcbState) t' s) \<and> t \<notin> set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> rva \<le> maxPriority \<and> rv \<le> maxDomain)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_bitmapQ_except rv rva s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s \<and> ((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (rv, rva) = []) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (valid_bitmapQ and (\<lambda>sa. (ksReadyQueues sa (rv, rva) = []) = (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) = []))) s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L2_orphans s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L1_orphans s) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L1_orphans s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (\<forall>d p. t \<notin> set (((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (d, p)))) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (\<forall>d p. t \<notin> set (((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (d, p))))) \<circ> tcbPriority) t s) \<circ> tcbDomain) t s else (\<lambda>s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s)) s) \<circ> tcbQueued) t s proof (prove)
goal (1 subgoal):
 1. \<And>s. (valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t) s \<Longrightarrow> tcb_at' t s \<and> obj_at' ((\<lambda>rv. (if rv then \<lambda>s. tcb_at' t s \<and> obj_at' ((\<lambda>rv. tcb_at' t s \<and> obj_at' ((\<lambda>rva. (((((filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_queues_no_bitmap_except t s \<and> (\<forall>t'\<in>set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))). obj_at' (inQ rv rva and runnable' \<circ> tcbState) t' s) \<and> t \<notin> set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> rva \<le> maxPriority \<and> rv \<le> maxDomain) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_queues_no_bitmap_except t s \<and> (\<forall>t'\<in>set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))). obj_at' (inQ rv rva and runnable' \<circ> tcbState) t' s) \<and> t \<notin> set (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva))) \<and> rva \<le> maxPriority \<and> rv \<le> maxDomain)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> valid_bitmapQ_except rv rva s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s \<and> ((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (rv, rva) = []) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (valid_bitmapQ and (\<lambda>sa. (ksReadyQueues sa (rv, rva) = []) = (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) = []))) s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L2_orphans s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L1_orphans s) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> bitmapQ_no_L1_orphans s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (\<forall>d p. t \<notin> set (((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (d, p)))) \<and> (\<not> filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)) \<noteq> [] \<or> (\<forall>d p. t \<notin> set (((ksReadyQueues s)((rv, rva) := filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (rv, rva)))) (d, p))))) \<circ> tcbPriority) t s) \<circ> tcbDomain) t s else (\<lambda>s. valid_queues_no_bitmap s \<and> valid_bitmapQ s \<and> bitmapQ_no_L2_orphans s \<and> bitmapQ_no_L1_orphans s)) s) \<circ> tcbQueued) t s proof (prove)
goal (1 subgoal):
 1. \<And>s ko. \<lbrakk>valid_queues_no_bitmap_except t s; valid_bitmapQ s; bitmapQ_no_L2_orphans s; bitmapQ_no_L1_orphans s; correct_queue t s; ko_at' ko t s; tcbDomain ko \<le> maxDomain; tcbPriority ko \<le> maxPriority\<rbrakk> \<Longrightarrow> (tcbQueued ko \<longrightarrow> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> valid_bitmapQ_except (tcbDomain ko) (tcbPriority ko) s) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (ksReadyQueues s (tcbDomain ko, tcbPriority ko) = []) = (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [])) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p))))) \<and> (\<not> tcbQueued ko \<longrightarrow> valid_queues_no_bitmap s) proof (prove)
goal (1 subgoal):
 1. \<And>s ko. \<lbrakk>valid_queues_no_bitmap_except t s; valid_bitmapQ s; bitmapQ_no_L2_orphans s; bitmapQ_no_L1_orphans s; \<forall>d p. t \<in> set (ksReadyQueues s (d, p)) \<longrightarrow> obj_at' (\<lambda>tcb. tcbQueued tcb \<and> tcbDomain tcb = d \<and> tcbPriority tcb = p) t s; ko_at' ko t s; tcbDomain ko \<le> maxDomain; tcbPriority ko \<le> maxPriority\<rbrakk> \<Longrightarrow> (tcbQueued ko \<longrightarrow> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> valid_bitmapQ_except (tcbDomain ko) (tcbPriority ko) s) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (ksReadyQueues s (tcbDomain ko, tcbPriority ko) = []) = (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [])) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p))))) \<and> (\<not> tcbQueued ko \<longrightarrow> valid_queues_no_bitmap s) proof (prove)
goal (1 subgoal):
 1. \<And>s ko. \<lbrakk>valid_queues_no_bitmap_except t s; valid_bitmapQ s; bitmapQ_no_L2_orphans s; bitmapQ_no_L1_orphans s; \<forall>d p. t \<in> set (ksReadyQueues s (d, p)) \<longrightarrow> tcbQueued ko \<and> tcbDomain ko = d \<and> tcbPriority ko = p; tcbDomain ko \<le> maxDomain; tcbPriority ko \<le> maxPriority; ko_at' ko t s\<rbrakk> \<Longrightarrow> (tcbQueued ko \<longrightarrow> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s)) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>t'. t' \<in> set (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) \<and> t' \<noteq> t \<longrightarrow> obj_at' (inQ (tcbDomain ko) (tcbPriority ko) and runnable' \<circ> tcbState) t' s) \<and> distinct (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> valid_bitmapQ_except (tcbDomain ko) (tcbPriority ko) s) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (ksReadyQueues s (tcbDomain ko, tcbPriority ko) = []) = (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [])) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<longrightarrow> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p)))) \<and> (filter (\<lambda>x. x \<noteq> t) (ksReadyQueues s (tcbDomain ko, tcbPriority ko)) = [] \<or> (\<forall>d p. (d = tcbDomain ko \<longrightarrow> p \<noteq> tcbPriority ko) \<longrightarrow> t \<notin> set (ksReadyQueues s (d, p))))) \<and> (\<not> tcbQueued ko \<longrightarrow> valid_queues_no_bitmap s) proof (prove)
goal:
No subgoals! proof (state)
this:
\<lbrace>valid_queues_no_bitmap_except t and valid_bitmapQ and bitmapQ_no_L2_orphans and bitmapQ_no_L1_orphans and correct_queue t and obj_at' (\<lambda>tcb. tcbDomain tcb \<le> maxDomain \<and> tcbPriority tcb \<le> maxPriority) t\<rbrace> tcbSchedDequeue t \<lbrace>\<lambda>_. Invariants_H.valid_queues\<rbrace>

goal:
No subgoals!