| (∃ r, value. r ≠ null ∧ ps = ∅[r, mk(value, Some(dummytid), null)] ∧ phead = r ∧ vhead = r ∧ vtail = r ∧ orl = r ' ∧ qrl = [] ∧ vs = ps) ∧ vrvHp = ∅ ∧ prvHp = ∅ ∧ vretRefs = (λ tid. null) ∧ pretRefs = (λ tid. null) ∧ owns = (λ r. None) ⊦ listp(orl + qrl, vs, ps, owns) ∧ ¬ dups(orl + qrl) ∧ markedp(orl, ps) ∧ markedp(orl, vs) ∧ unmarkedp(qrl, ps) ∧ orl ≠ [] ∧ phead ∈ orl ∧ rvownerok(vretRefs, vrvHp, rvowns) ∧ allocrv(vretRefs, vrvHp) ∧ nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs) ∧ rvownerok(pretRefs, prvHp, rvowns) ∧ allocrv(pretRefs, prvHp) ∧ dom vrvHp = dom prvHp ∧ ( vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val)) ∧ (orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs)) ∧ (vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[(orl + qrl).last].next = null) |
owns = (λ r. None), pretRefs = (λ tid. null), prvHp = ∅, vretRefs = (λ tid. null), vrvHp = ∅, ∃ r, value. r ≠ null ∧ ps = ∅[r, mk(value, Some(dummytid), null)] ∧ phead = r ∧ vhead = r ∧ vtail = r ∧ orl = r ' ∧ qrl = [] ∧ vs = ps ⊦ listp(orl + qrl, vs, ps, owns) ∧ ¬ dups(orl + qrl) ∧ markedp(orl, ps) ∧ markedp(orl, vs) ∧ unmarkedp(qrl, ps) ∧ orl ≠ [] ∧ phead ∈ orl ∧ rvownerok(vretRefs, vrvHp, rvowns) ∧ allocrv(vretRefs, vrvHp) ∧ nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs) ∧ rvownerok(pretRefs, prvHp, rvowns) ∧ allocrv(pretRefs, prvHp) ∧ dom vrvHp = dom prvHp ∧ ( vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val)) ∧ (orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs)) ∧ (vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[(orl + qrl).last].next = null)
| owns = (λ r. None), pretRefs = (λ tid. null), prvHp = ∅, vretRefs = (λ tid. null), vrvHp = ∅, ∃ r, value. r ≠ null ∧ ps = ∅[r, mk(value, Some(dummytid), null)] ∧ phead = r ∧ vhead = r ∧ vtail = r ∧ orl = r ' ∧ qrl = [] ∧ vs = ps ⊦ listp(orl + qrl, vs, ps, owns) ∧ ¬ dups(orl + qrl) ∧ markedp(orl, ps) ∧ markedp(orl, vs) ∧ unmarkedp(qrl, ps) ∧ orl ≠ [] ∧ phead ∈ orl ∧ rvownerok(vretRefs, vrvHp, rvowns) ∧ allocrv(vretRefs, vrvHp) ∧ nonullRetRefs(orl + qrl, vs, vretRefs, pretRefs) ∧ rvownerok(pretRefs, prvHp, rvowns) ∧ allocrv(pretRefs, prvHp) ∧ dom vrvHp = dom prvHp ∧ ( vs[vhead].next ≠ null ∧ vs[vs[vhead].next].deqID ≠ None → rvowns(vretRefs(vs[vs[vhead].next].deqID.tid)) = Claimed(vs[vs[vhead].next].deqID.tid, vs[vs[vhead].next].val)) ∧ (orl.last = vhead ∧ (qrl ≠ [] → unmarkedp(qrl.tail, vs)) ∨ orl.butlast ≠ [] ∧ orl.butlast.last = vhead ∧ phead ≠ orl.last ∧ unmarkedp(qrl, vs)) ∧ (vtail = (orl + qrl).last ∨ qrl ≠ [] ∧ vtail = (orl + qrl.butlast).last ∧ vs[qrl.last].deqID = None ∧ vs[(orl + qrl).last].next = null) |
r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ rvownerok(λ tid. null, ∅, rvowns) ∧ allocrv(λ tid. null, ∅)
Used simplifier rules: ⊦ a '.last = a; (s) a: ⊦ (x + y) + z = x + y + z; from specification list[reflist] ⊦ x + [] = x; (s) ⊦ mk(val, opttid, nxt).next = nxt; (s) ⊦ a = b → st[b, d][a] = d; (s) ⊦ a ∈ b ' ↔ a = b; (s) ⊦ a ' ≠ []; (s) ⊦ unmarkedp([], vs); (s) ⊦ some?(Some(tid)); (s) ⊦ mk(val, opttid, nxt).deqID = opttid; (s) ⊦ markedp(r ', vs) ↔ some?(vs[r].deqID); (s) ⊦ ¬ dups(a '); (s) ⊦ ¬ weak?(Some(tid)); (s) ⊦ a ∈ st[a, d]; (s) ⊦ listp(r ', vs, ps, owns) ↔ owns(r) = None ∧ r ∈ vs ∧ r ∈ ps ∧ r ≠ null ∧ ¬ weak?(vs[r].deqID) ∧ (ps[r].deqID = vs[r].deqID ∨ ps[r].deqID = None) ∧ ps[r].val = vs[r].val ∧ ps[r].next = null ∧ ( vs[r].next ≠ null → vs[r].next ∈ vs ∧ vs[r].next ∈ ps ∧ ps[vs[r].next] = vs[vs[r].next] ∧ ps[vs[r].next].deqID = None ∧ ps[vs[r].next].next = null ∧ weak?(owns(vs[r].next))); (s)
| r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ rvownerok(λ tid. null, ∅, rvowns) ∧ allocrv(λ tid. null, ∅) |
⊦ rvownerok(vretRefs, vrvHp, rvowns) ↔ (∀ tid. vretRefs(tid) ≠ null → vretRefs(tid) ∈ vrvHp ∧ rvowns(vretRefs(tid)).tid = tid)
r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ (∀ tid. null ≠ null → null ∈ ∅ ∧ rvowns(null).tid = tid) ∧ allocrv(λ tid. null, ∅)
Used terms: λ tid. null, ∅, rvowns
| ⊦ rvownerok(vretRefs, vrvHp, rvowns) ↔ (∀ tid. vretRefs(tid) ≠ null → vretRefs(tid) ∈ vrvHp ∧ rvowns(vretRefs(tid)).tid = tid) |
| r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ (∀ tid. null ≠ null → null ∈ ∅ ∧ rvowns(null).tid = tid) ∧ allocrv(λ tid. null, ∅) |
r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ allocrv(λ tid. null, ∅)
| r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ allocrv(λ tid. null, ∅) |
⊦ allocrv(vretRefs, vrvHp) ↔ (∀ tid. vretRefs(tid) = null ∨ vretRefs(tid) ∈ vrvHp ∧ vretRefs(tid) ≠ null)
r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ (∀ tid. null = null ∨ null ∈ ∅ ∧ null ≠ null)
Used terms: λ tid. null, ∅
| ⊦ allocrv(vretRefs, vrvHp) ↔ (∀ tid. vretRefs(tid) = null ∨ vretRefs(tid) ∈ vrvHp ∧ vretRefs(tid) ≠ null) |
| r ≠ null ⊦ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ∧ (∀ tid. null = null ∨ null ∈ ∅ ∧ null ≠ null) |
r ≠ null, ¬ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ⊦
| r ≠ null, ¬ nonullRetRefs(r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null) ⊦ |
⊦ nonullRetRefs(rl, vs, vretRefs, pretRefs) ↔ (∀ r. r ∈ rl ∧ r ≠ rl.head ∧ vs[r].deqID ≠ None → vretRefs(vs[r].deqID.tid) ≠ null ∧ pretRefs(vs[r].deqID.tid) ≠ null)
Used simplifier rules: ⊦ a '.head = a; (s) ⊦ a ≠ b → st[b, d][a] = st[a]; (s) ⊦ a ∈ b ' ↔ a = b; (s) Used terms: r ', ∅[r, mk(value, Some(dummytid), null)], λ tid. null, λ tid. null
| ⊦ nonullRetRefs(rl, vs, vretRefs, pretRefs) ↔ (∀ r. r ∈ rl ∧ r ≠ rl.head ∧ vs[r].deqID ≠ None → vretRefs(vs[r].deqID.tid) ≠ null ∧ pretRefs(vs[r].deqID.tid) ≠ null) |
The following image shows the proof tree of sequent calculus. The proved goal is at the bottom. You can click on the nodes to view additional rules. See here for details on colors in a proof tree.